水果成篮 图解题解

这道题到底在问什么

fruits

[1,2,3,2,2]

输出

4

解释

摘 [2,3,2,2](下标 1~4),只有 2、3 两种

先想最直接的笨办法

暴力第一趟:从下标 0 出发,先摘到 1,篮子里有种类 {1}。继续往右看。（动画第 4 步）

最优解：一步一步想明白

1. 3先想最直白的:从每棵树都试着往右摘到摘不动为止。能算对,但每个起点都重新扫一遍,数据一大就慢。下面看怎么省掉重复。
2. 4起点固定 0,往右扫暴力第一趟:从下标 0 出发,先摘到 1,篮子里有种类 {1}。继续往右看。
3. 5遇到 3 → 第 3 种,停摘到下标 2 的 3 时,种类变成 {1,2,3} 三种,超了!起点 0 这趟最多摘 [1,2] 长度 2。接着起点挪到 1 重头再扫——这就是重复劳动。
4. 6起点 1,又从头数种类起点挪到 1,前面的 0 号格不要了(变灰),又从头开始数种类:先摘 2,种类 {2}。注意 [1,2] 这段区间刚才已经数过一遍了,现在还要再数——重复就出在这。
5. 7摘到 3 → 第 2 种起点 1 往右摘到下标 2 的 3,种类 {2,3} 两种,还合法,接着往右。
6. 82、2 都已有种,合法起点 1 这趟运气好,后面 2、2 都已在篮子里,一路只有 {2,3} 两种,摘到末尾长度 4。但要这样把每个起点都重扫一遍,n 大就是 O(n²)。下面看怎么只扫一遍。
7. 9关键发现:左右指针都只往右走、绝不回头。右指针每次进一个新水果,只有当种类超过 2 时,才从左边挤出水果。这样整排树只扫一遍 → O(n)。
8. 10盯住三样东西:左指针 l、右指针 r、还有计数表里的种类数。下面一帧一个动作走一遍 [1,2,3,2,2]。
9. 11l=r=0,篮子空开局两根指针 l、r 都停在 0,篮子还空着。接下来右指针每走一格,就把那格水果装进计数表。
10. 12r=0,装入 1右指针把 0 号格的 1 装进篮子,计数表 {1:×1},1 种 ≤ 2 合法。窗口 [0,0] 长 1,最长记 1。
11. 13r 入窗,装 2r 右移到 1,把 2 装进来,计数表 {1:×1, 2:×1},正好 2 种,两个篮子都用上了,还合法。窗口长 2,最长更新成 2。
12. 14装 3 → 第 3 种r 移到 2,把 3 装进来,计数表变 {1:×1, 2:×1, 3:×1} 三种,超过 2 个篮子!现在不能更新答案,得从左边挤水果,直到只剩 2 种。
13. 15fruits[l]=1 减到 ×0缩左第一步:看 l 当前指着的水果 1,把它的计数减 1 变 ×0。计数到 0 说明窗口里这种水果一个都不剩了,下一步该把这个键删掉。
14. 16删掉 1,l → 1缩左第二步:把计数为 0 的 1 从表里删掉,l 右移到 1,0 号格被挤出变灰。计数表 {2:×1, 3:×1} 回到 2 种,窗口 [1,2] 重新合法,长 2。
15. 17装 2,数量 +1r 移到 3,又是个 2,已经在篮子里,只是个数 +1,计数表 {2:×2, 3:×1},还是 2 种。窗口长 3,最长刷新成 3!
16. 18再装 2,数量 +1r 移到 4,还是 2,个数再 +1,计数表 {2:×3, 3:×1},仍是 2 种。窗口长到 4,最长刷新成 4!这就是答案区间 [2,3,2,2]。
17. 19扫完,最长 = 4r 走到数组末尾,结束。整趟下来最长合法窗口是 [1,4],绿色这四格 [2,3,2,2] 就是答案 4。l 和 r 各自只往右走了一遍。
18. 20l=0 r=0,装 0换串 [0,1,2,2] 再走一遍。l、r 都在 0,装 0,计数 {0:×1},长 1。
19. 21装 1,凑满 2 种r 到 1,装 1,计数 {0:×1, 1:×1},两种装满,长 2,最长记 2。
20. 22装 2 → 3 种r 到 2 装进 2,计数 {0:×1, 1:×1, 2:×1} 三种超标,得缩左。
21. 230 减到 ×0 删键,l → 1缩左把 l 处的 0 减到 ×0 并删键,l 右移到 1,计数回到 {1:×1, 2:×1},窗口 [1,2] 合法,长 2。
22. 24装 2,数量 +1r 到 3,又是 2 只是个数 +1,计数 {1:×1, 2:×2},长 3,最长刷成 3。绿色 [1,2,2] 就是这串的答案。
23. 25为什么是 O(n) 不是 O(n²)?因为 r 走 n 步,l 一辈子加起来也最多走 n 步,合计 2n 次操作——线性。这就是滑动窗口比暴力快的根。
24. 29count 留着 0 → 种类虚高假如缩左时把 1 减到 0 却忘了删键,计数表里还留着 {1:×0},种类数被误算成 3,窗口怎么缩都 >2 种,答案直接崩——这就是必须删键的原因。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def totalFruit(self, fruits):
        count = {}
        left = 0
        best = 0
        for right in range(len(fruits)):
            f = fruits[right]
            count[f] = count.get(f, 0) + 1   # r 入窗
            while len(count) > 2:            # 超 2 种 → 缩左
                lf = fruits[left]
                count[lf] -= 1
                if count[lf] == 0:
                    del count[lf]
                left += 1
            best = max(best, right - left + 1)
        return best

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> count;
        int left = 0, best = 0;
        for (int right = 0; right < (int)fruits.size(); right++) {
            count[fruits[right]]++;          // r 入窗
            while ((int)count.size() > 2) {  // 超 2 种 → 缩左
                int lf = fruits[left];
                if (--count[lf] == 0) count.erase(lf);
                left++;
            }
            best = max(best, right - left + 1);
        }
        return best;
    }
};

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < fruits.length; right++) {
            int f = fruits[right];
            count.put(f, count.getOrDefault(f, 0) + 1);  // r 入窗
            while (count.size() > 2) {                   // 超 2 种 → 缩左
                int lf = fruits[left];
                count.put(lf, count.get(lf) - 1);
                if (count.get(lf) == 0) count.remove(lf);
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

复杂度

面试官可能追问