LeetCode 904. 水果成篮

2024-10-16 HGNULB 约 12 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 904. 水果成篮

题意分析

一排果树，fruits[i] 是第 i 棵树上水果的种类。你有两个篮子，每个篮子只能装一种水果，数量不限。规则是：从任选的一棵树开始，向右不停顿地采摘，每棵树必须摘且只摘一个，遇到装不下的水果就必须停止。问最多能摘到多少个水果。

把这段故事翻译一遍：两个篮子 = 最多两种水果；从某棵树开始向右不停顿 = 一段连续的子数组；求最多摘多少个 = 求这段子数组的最大长度。所以题目等价于——

在数组中找一个最长的连续子数组，使得其中不同元素的种类数不超过 2。

完成这层翻译，题目就从「读故事」变成了一道模板题。这也是这道题真正的考点：识别出「连续 + 带约束 + 求最长」这三个特征的组合。

「连续」排除了排序、排除了任意取子集；「求最长」而不是「求个数」意味着我们只需要维护一个最优值；「约束是种类数上限」而且这个约束具有单调性——一个合法窗口的任意子窗口也一定合法（子集的种类数不会更多）。这三条加在一起，正是滑动窗口的适用条件。

约束透露的信号：数组长度在 $10^5$ 量级，元素值可以大到 $10^5$。长度决定了 $O(n^2)$ 的枚举起点做法（$10^{10}$）必然超时，只能上线性；元素值域很大则说明不能用定长数组当计数器（虽然开 $10^5$ 也不是不行，但哈希表更自然，且窗口内最多只有 3 个键）。

边界：数组只有一个元素时答案是 1；整个数组只有一两种水果时答案就是数组长度，窗口从不收缩；fruits 保证非空，不必处理空数组；答案至少为 1，所以初值取 0 也不会出错。

解法：滑动窗口统计两类水果

核心思路

先看暴力：枚举所有的起点 i，从 i 向右扩展并用一个集合记录种类，种类超过 2 就停下，记录长度。时间 $O(n^2)$，$10^5$ 的规模下是 $10^{10}$ 次操作，稳定超时。瓶颈在于：起点右移一格后，前一轮扫描过的绝大部分区间被完全丢弃、从头再来，而这些区间的信息本可以继承。

能继承的依据是一条单调性质：若以 i 为起点的最远合法终点是 r，那么以 i+1 为起点的最远合法终点一定不小于 r。因为 [i+1, r] 是 [i, r] 的子区间，种类数只会更少或相等，必然仍合法。既然右端点永不回头，左右两个指针就都只需要单向移动，总移动次数是 $O(n)$——这就是滑动窗口能成立的根本原因，也是它区别于「双重循环」的关键。

于是采用「右端点主动扩张、左端点被动收缩」的框架，用一个哈希表 count 维护窗口内每种水果的出现次数。核心不变量是：

在每一轮循环体的末尾，窗口 [left, right] 内的水果种类数不超过 2，且 count 恰好记录了这个窗口内每种水果的出现次数（键的个数就是种类数）。

每一轮做三件事。第一，右端点前进一格，把 fruits[right] 的计数加一——此时种类数最多变成 3，因为一次只新增一个元素。第二，只要 count.size() > 2，就把 fruits[left] 的计数减一、若减到 0 就从表中删除该键，然后 left++；这一步用 while 而不是 if，虽然本题里种类数一次最多超 1、循环体实际只会执行到恰好合法，但写成 while 才与「收缩到合法为止」的语义严格对应，也能无缝迁移到「最多 K 种」的推广题。第三，此刻窗口已经合法，用 right - left + 1 更新答案。

有两个细节值得单独强调。

其一，计数归零必须删除键，不能只把值置为 0。因为我们是用 count.size() 来代表「种类数」的，一个值为 0 的键仍然占据 size，会让窗口被误判为不合法而过度收缩，答案偏小。如果不想删键，就得额外维护一个 distinct 计数变量，那样反而更容易写漏。

其二，答案的更新必须放在收缩之后。收缩前的窗口可能是非法的（含 3 种水果），拿它的长度去更新会得到偏大的错误答案。「先扩张、再收缩到合法、最后结算」这个三段式顺序，是所有「求最长合法窗口」类题目的统一骨架。

解题步骤

准备哈希表 count、左指针 left = 0、答案 answer = 0。为什么 answer 初值取 0：数组保证非空，答案至少是 1，第一轮循环就会把它更新掉；取 0 既是长度的下界，也让空输入（若允许）自然返回 0。

右指针 right 从 0 遍历到末尾，先执行 count[fruits[right]]++。为什么先加入再判断：滑动窗口的标准节奏是「无条件纳入新元素，再修复可能被破坏的约束」；若先判断能不能加，就要预先查询该元素是否已在窗口内，逻辑分支立刻变多。

while (count.size() > 2) 时收缩左边界。为什么条件是 > 2 而不是 >= 2：题目允许恰好两种水果，两个篮子是上限不是下限；写成 >= 2 会把所有含两种水果的窗口都收掉，答案退化成「最长的单一种类连续段」。

收缩时先把 fruits[left] 的计数减一，减到 0 就 remove 掉这个键，然后 left++。为什么必须删键：count.size() 是我们唯一的种类数来源，残留的零值键会虚增种类数，导致窗口被过度收缩。为什么 left++ 放在最后：减计数用的是 fruits[left]，指针必须在用完之后才推进。

收缩结束后用 right - left + 1 更新 answer。为什么长度是 right - left + 1：[left, right] 是闭区间，元素个数比下标差多 1。为什么在收缩后更新：收缩前窗口可能含 3 种水果，是非法状态，不能参与答案。

遍历结束返回 answer。为什么不需要在循环外补一次结算：每一轮都在合法状态下结算过了，最优值不会被漏掉。

以 具体用例 fruits = [1, 2, 3, 2, 2] 走一遍，预期答案是 4，对应子数组 [2, 3, 2, 2]。

初始：count = {}，left = 0，answer = 0。

right = 0（水果 1）：count = {1:1}，种类数 1，不超过 2，无需收缩。窗口是 [0,0]，长度 0-0+1 = 1，answer 更新为 1。
right = 1（水果 2）：count = {1:1, 2:1}，种类数 2，恰好达到上限但合法，不收缩。窗口 [0,1]，长度 2，answer 更新为 2。这里正是「条件写 > 2 而非 >= 2」的体现。
right = 2（水果 3）：count = {1:1, 2:1, 3:1}，种类数 3，超限，进入收缩。取 fruits[left] = fruits[0] = 1，计数从 1 减到 0，删除键 1，count = {2:1, 3:1}，left 变为 1。此时种类数回到 2，退出收缩。窗口 [1,2]，长度 2-1+1 = 2，answer 保持 2。若这一步只把计数置 0 而不删键，count.size() 仍是 3，循环会继续把 2 也剔掉，窗口被过度收缩到 [2,2]，后续答案会一路偏小。
right = 3（水果 2）：count = {2:2, 3:1}，种类数 2，合法。窗口 [1,3]，长度 3-1+1 = 3，answer 更新为 3。
right = 4（水果 2）：count = {2:3, 3:1}，种类数 2，合法。窗口 [1,4]，长度 4-1+1 = 4，answer 更新为 4。

遍历结束，返回 4。对应的窗口是下标 1 到 4，即 [2,3,2,2]，两个篮子分别装水果 2 和水果 3，共摘 4 个，与预期一致。

顺带验证一下左指针的单向性：整个过程中 left 只从 0 走到 1，right 从 0 走到 4，两者合计移动 5 次，正是 $O(n)$ 的来源——没有任何一个下标被重复扫描。

代码实现

class Solution {
    // 右端点每前进一步只会增加一种水果，适合用计数表维护窗口内出现的种类数。
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0;
        int answer = 0;

        for (int right = 0; right < fruits.length; right++) {
            count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);

            while (count.size() > 2) {
                count.put(fruits[left], count.get(fruits[left]) - 1);
                if (count.get(fruits[left]) == 0) {
                    count.remove(fruits[left]);
                }
                left++;
            }

            answer = Math.max(answer, right - left + 1);
        }

        return answer;
    }
}

func totalFruit(fruits []int) int {
    // 右端点每前进一步只会增加一种水果，适合用计数表维护窗口内出现的种类数。
    window := make(map[int]int)
    left := 0
    answer := 0

    for right, v := range fruits {
        window[v]++
        for len(window) > 2 {
            window[fruits[left]]--
            if window[fruits[left]] == 0 {
                delete(window, fruits[left])
            }
            left++
        }
        if right-left+1 > answer {
            answer = right - left + 1
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n)$。凭什么：right 显然只从 0 走到 $n-1$；left 是关键——它只增不减，整个过程中最多向右移动 $n$ 次，所以那个看似嵌套的 while 循环在整轮遍历中的总执行次数被 left 的总位移量所限制，是均摊 $O(1)$ 而非每轮 $O(n)$。哈希表的插入、查询、删除都是均摊常数。这正是滑动窗口区别于双重循环的地方：形式上有嵌套，实质上是两个各走一遍的指针。

空间复杂度：$O(1)$。凭什么：count 在任意时刻最多只有 3 个键——窗口合法时是 2 个，刚扩张完尚未收缩时短暂为 3 个，之后立刻被压回 2 个。键的数量由题目的「两个篮子」硬性封顶，与数组长度和值域都无关。如果推广成「最多 K 种」，空间才会变成 $O(K)$。

关键点总结

先把故事翻译成数组语言，再选算法。「两个篮子」= 种类数上限 2，「不停顿地向右采摘」= 连续子数组，「最多摘多少」= 最大长度。绝大多数包装题的难点都在这层翻译上，翻译完成后往往就是模板题。

滑动窗口的适用条件是约束的单调性：合法窗口的任意子窗口也合法。有了这条，左端点右移时右端点不必回退，两个指针各走一遍，$O(n)$ 才成立。做题时应当先默念一遍这条性质是否满足——例如把约束换成「窗口内元素和恰好等于 K 且允许负数」，单调性就没了，滑窗立刻失效。

「扩张 → 收缩到合法 → 结算」的三段式顺序不能乱。求最长合法窗口时结算必须在收缩之后；而求「最短合法窗口」（如 76 题）时结算要放在收缩循环的内部。搞清自己在求最长还是最短，决定了结算语句该放哪一行。

用容器大小代表「种类数」时，计数归零必须删键。这是本题最高频的错误。若嫌删键麻烦，就改为维护一个独立的 distinct 变量，在计数从 0 变 1 时加一、从 1 变 0 时减一——两种写法二选一，混着写必错。

收缩用 while 而不是 if。本题因为一次只新增一个元素，if 恰好也能过；但写成 while 才与「收缩到重新合法为止」的语义一致，推广到「最多 K 种」或一次加入多个元素的变体时才不会崩。

面试视角：这题几乎必定会被追问「如果篮子有 K 个呢」——答案是把 > 2 改成 > k，其余一字不动，这也是 340. 至多包含 K 个不同字符的最长子串的原题。能主动指出「本题是 K = 2 的特例」并说清哈希表的空间从 $O(1)$ 变成 $O(K)$，比只写出代码更能体现你掌握的是模式而非答案。另一个常见追问是「为什么内层 while 不会让复杂度变成 $O(n^2)$」，务必用「left 单调不减、总位移不超过 $n$」来回答，而不是含糊地说「一般不会跑那么多次」。

易错点总结

错误写法：计数减到 0 时只 put(key, 0) 而不 remove(key) → 用例 fruits = [1,2,3,2,2]，right = 2 收缩时键 1 的值变为 0 但仍留在表中，count.size() 依旧是 3，循环继续把键 2 也剔掉，窗口被过度收缩到 [2,2]；最终答案变成 3 而不是 4。

错误写法：收缩条件写成 while (count.size() >= 2) → 用例 fruits = [1,2,1,2]，任何含两种水果的窗口都会被收掉，答案退化成最长的单一种类段，返回 1；正确答案是 4。两个篮子是上限，恰好用满是合法的。

错误写法：把 answer 的更新放在收缩之前 → 用例 fruits = [1,2,3,2,2]，right = 2 时窗口 [0,2] 含 3 种水果、长度 3，在收缩前结算会得到 3；虽然本例最终答案 4 更大而侥幸不受影响，但换成 fruits = [1,2,3] 时会返回 3，正确答案是 2。

错误写法：left++ 写在计数减一之前 → 用例 fruits = [1,2,3]，收缩时先把 left 推到 1，再去减 count[fruits[1]] 即水果 2 的计数，被移出窗口的其实是水果 1，计数表与窗口内容彻底失配，后续所有判断都是错的。

错误写法：窗口长度写成 right - left → 用例 fruits = [1]，left = right = 0，算出长度 0，返回 0；正确答案是 1。闭区间的长度是下标差加一。

错误写法：用两个变量 f1、f2 记录两种水果，遇到第三种就把 left 直接跳到 right → 用例 fruits = [1,2,3,2,2]，right = 2 时把 left 跳到 2，丢掉了本该保留的水果 2（下标 1），窗口起点错误，最终答案为 3 而非 4。收缩必须逐格进行，只能剔掉最左那一种水果，不能把整个窗口清空。

错误写法：用 int[100001] 定长数组当计数器，同时用「遍历整个数组数非零项」来求种类数 → 逻辑正确但每轮都要扫 $10^5$ 个格子，总复杂度 $10^{10}$，直接超时。定长数组本身没问题，但必须配一个独立的 distinct 变量增量维护种类数。

错误写法：外层 for 改成 while (right < n) 但在收缩分支里忘记 right++ → 任意含三种以上水果的用例都会死循环：种类数超限后 left 一路推到 right，此时 count.size() 变为 1、退出收缩，但 right 从未推进，下一轮又把同一个元素加进来。用 for 循环让 right 的推进无条件发生，是规避这类死循环的最简办法。

错误写法：收缩用 if 而非 while，并把这个写法直接迁移到「最多 K 种」的变体 → 用例 fruits = [1,2,3,4]、k = 1 时，right = 1 处种类数从 1 涨到 2，if 只收缩一次恰好够；但若一次加入多个元素或初始就超限，单次收缩无法恢复合法，窗口长期处于非法状态，答案偏大。

错误写法：Go 中写 delete(window, fruits[left]) 之后才 window[fruits[left]]-- → 删除后再自减会重新插入一个值为 -1 的键，len(window) 不减反增，收缩循环永远退不出去，程序死循环。

相似题目

题目	难度	考察点
159. 至多包含两个不同字符的最长子串	中等	与本题完全同构，只是把水果换成字符，可原样套用同一份代码
340. 至多包含 K 个不同字符的最长子串	中等	本题的一般化，把 `> 2` 改成 `> k` 即可，空间随之变成 $O(K)$
3. 无重复字符的最长子串	中等	约束变成「每种字符至多一个」，可以让左指针直接跳到重复字符的下一位而非逐格挪
1004. 最大连续1的个数 III	中等	约束是「窗口内 0 的个数不超过 K」，用一个计数变量即可，不需要哈希表
424. 替换后的最长重复字符	中等	约束依赖「窗口长度减去最高频字符数」，难点在最高频数无需精确回退也不影响答案
1493. 删掉一个元素以后全为 1 的最长子数组	中等	至多允许一个 0，且答案要减一，考的是「必须删一个」这条额外语义
76. 最小覆盖子串	困难	求最短合法窗口，结算语句要移进收缩循环内部，与本题的结算位置恰好相反
438. 找到字符串中所有字母异位词	中等	窗口长度固定，左右指针同步移动，不存在「收缩到合法」的过程
567. 字符串的排列	中等	同为定长窗口，但只需判断存在性，可用一个 `matched` 计数器代替逐项比对频次