LC904. 水果成篮

题目描述

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果： 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1： 输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。 示例 2： 输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。 示例 3： 输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。 示例 4： 输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示： 1 <= fruits.length <= 10^(5) 0 <= fruits[i] < fruits.length

题目解析

好的，没问题。我们一起来把这道题彻底搞懂。

题目在说什么

想象一下，你走进了一个果园。果园里有一排树，从左到右排成一排。每棵树上都结了一种水果，我们用数字来表示水果的种类，比如 1 代表苹果，2 代表梨，3 代表桃子。

你的任务是用两个篮子去摘水果。规则有点特别：

1. 两个篮子，两种水果：你只有两个篮子。而且，每个篮子只能装 同一种 水果。比如，一个篮子专门装苹果，另一个篮子专门装梨。你不能混着装。 2. 从某棵树开始，一直往右走：你可以选择从任何一棵树开始。然后，你必须一棵接一棵地往右走，每经过一棵树，就要从这棵树上摘一个水果放到篮子里。 3. 必须符合篮子里的种类：你篮子里的水果种类，最多只能有两种（因为只有两个篮子）。所以，你只能摘那些种类在你当前两个篮子里的水果。 4. 遇到新种类就停：如果你走到一棵树前，发现这棵树的水果种类，既不是篮子1里的，也不是篮子2里的（也就是出现了第三种水果），那你就必须立刻停止采摘。你不能再往前走了。

题目问的是：在遵守这些规则的前提下，你最多能摘到多少个水果？也就是，找到一个连续的果树序列，这个序列里最多只包含两种不同的水果，并且这个序列要尽可能长。

思路是怎么来的

这个“连续”和“最多两种”的要求，一下子就让我们想到了一个经典的算法技巧：滑动窗口。

什么是滑动窗口？

你可以把它想象成一个可以伸缩的“取景框”。这个框子从左到右在果树序列上滑动。框子的左边界和右边界就是你想采摘的起始树和结束树。

• 右边界：负责“探索”，不断向右移动，尝试把新的树框进来。
• 左边界：负责“收缩”，当框进来的水果种类超过了两种（也就是出现了第三种水果），我们就需要把左边界向右移动，丢掉一些左边的树，直到框子里的水果种类重新变回两种或以下。

为什么用滑动窗口？

因为我们要找的是连续的子序列。滑动窗口天生就是用来处理连续子数组/子串问题的。我们只需要维护一个窗口，保证窗口里始终只有最多两种水果，然后记录这个窗口的最大长度就行了。

生活化的比喻

想象你有一个能伸缩的“魔法口袋”，这个口袋只能装两种不同的水果。

1. 开始：你站在第一棵树前，把口袋打开，开始往右走。每遇到一棵树，就把它的水果放进口袋。 2. 遇到第三种：走着走着，你遇到了一种新水果，而你的口袋已经有两种水果了（比如苹果和梨）。这时候，口袋满了，装不下了。 3. 怎么办？ 你不能跳过这棵树，因为必须连续摘。所以，你必须从口袋的最左边开始，把最早放进去的那种水果全部扔掉，直到口袋里的水果种类重新变成两种（或者一种）。比如，你最早放进去的是苹果，你就得把所有的苹果都从口袋里拿出来，直到口袋里只剩下梨和这个新水果。 4. 继续前进：扔掉一些水果后，口袋又有空间了，你就可以把新水果放进去，然后继续往右走。 5. 记录最大：在整个过程中，你随时记录下口袋里水果的数量（也就是窗口的大小），并记住这个数量的最大值。这个最大值就是答案。

代码逐步拆解

我们来看一下用 Python 写的参考代码，并一步步解释。

class Solution:
    def totalFruit(self, fruits):
        # 1. 初始化
        left = 0  # 窗口的左边界
        fruit_count = {}  # 一个字典，用来记录窗口内每种水果有多少个
        max_fruits = 0  # 记录能摘到的最大水果数量

        # 2. 右边界开始向右移动（探索）
        for right in range(len(fruits)):
            # 3. 把当前这棵树的水果（fruits[right]）加进窗口
            fruit = fruits[right]
            # 如果字典里没有这种水果，就初始化数量为0，然后加1
            fruit_count[fruit] = fruit_count.get(fruit, 0) + 1

            # 4. 检查窗口是否“不合法”（水果种类超过2种）
            # 如果字典里记录的“键”（水果种类）的数量大于2，说明窗口不合法
            while len(fruit_count) > 2:
                # 5. 需要移动左边界，缩小窗口
                left_fruit = fruits[left]  # 获取左边界上的水果种类
                # 把这种水果的数量减1
                fruit_count[left_fruit] -= 1
                # 如果这种水果的数量变成了0，就从字典里删除它
                if fruit_count[left_fruit] == 0:
                    del fruit_count[left_fruit]
                # 左边界向右移动一位
                left += 1

            # 6. 现在窗口是合法的（最多2种水果），更新最大长度
            # 窗口的长度 = 右边界 - 左边界 + 1
            max_fruits = max(max_fruits, right - left + 1)

        # 7. 返回结果
        return max_fruits

逐步拆解：

1. 初始化：