904. 水果成篮

🎯 问题描述（来源于LeetCode）

描述：
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩：

你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果数量不限。
你可以选择任意一棵树开始采摘，但必须从这棵树开始依次向右采摘每棵树上的水果（即采摘连续的子数组）。
一旦你遇到某棵树上的水果不属于你篮子中的类型，你必须停止采摘。

给定一个整数数组 fruits，返回你可以收集的水果的最大数目。

说明：

这是一个不定长滑动窗口问题。
核心逻辑是维护一个窗口，使得窗口内不同水果种类的数量不超过 2 种。
当种类数量超过 2 时，收缩左边界。
示例：
示例 1：

1
2
3

输入：fruits = [1,2,1]
输出：3
解释：我们可以采摘 [1,2,1]，所有树都可以采摘。

示例 2：

1
2
3

输入：fruits = [0,1,2,2]
输出：3
解释：我们可以采摘 [1,2,2]。如果从第一棵树开始，我们会得到 [0,1]，然后遇到 2 必须停止。

示例 3：

1
2
3

输入：fruits = [1,2,3,2,2]
输出：4
解释：我们可以采摘 [2,3,2,2]。

💻 解题思路

思路1：不定长滑动窗口

思路1：代码实现

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        count = Counter()   # 哈希表，记录窗口内每种水果的数量
        ans = 0             # 记录最大采摘数量
        left = 0            # 窗口左边界
        
        # 右边界 right 随循环遍历数组
        for right, spies in enumerate(fruits):
            # 1. 扩展窗口：将当前水果加入哈希表
            count[spies] += 1
            
            # 2. 收缩窗口：如果水果种类超过 2 种
            # 则不断移动左边界，直到种类数恢复为 2 或更少
            while len(count) > 2:
                count[fruits[left]] -= 1
                # 如果某种水果数量归零，从哈希表中删除
                if count[fruits[left]] == 0:
                    del count[fruits[left]]
                left += 1
            
            # 3. 更新答案：此时窗口 [left, right] 内水果种类 <= 2
            ans = max(ans, right - left + 1)
            
        return ans

思路1：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是数组 fruits 的长度。
- 虽然代码中有一个 while 循环嵌套在 for 循环中，但每个元素最多被访问两次（一次被右边界 right 加入，一次被左边界 left 移出）。因此，整体操作次数是线性的。
空间复杂度： $O(1)$ $O (1)$
- 哈希表 count 最多存储 3 个键值对（在 while 循环判断前瞬间），因为一旦超过 2 就会收缩。所以空间复杂度是常数级别。

思考

问题转换：
- 题目本质是寻找最长连续子数组，使得子数组中不同元素的个数不超过 2。
- 这与“无重复字符的最长子串”（不同元素个数不超过 1）非常相似，只是阈值变成了 2。
哈希表维护：
- 使用 Counter 统计每种水果的数量。
- len(count) 直接反映了当前窗口内水果的种类数。
- 当移除元素时，必须检查数量是否归零，如果归零则 del 掉该键，以确保 len(count) 准确。
变量命名：
- 代码中使用了 spies 作为循环变量名，这可能是从类似的“间谍”题目复制过来的，但在逻辑上它代表当前树的水果类型 fruit_type。
收缩逻辑：
- while len(count) > 2: 保证了窗口的合法性。
- 只有当窗口内种类数合法时，才更新最大长度 ans。