题目

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 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

解题思路

题意分析

题目的要求是“从任意位置开始，连续采摘，但最多只能采摘两种水果”。这可以被转换成一个经典的数组问题：寻找一个最长的连续子数组，该子数组中最多只包含两种不同的元素。

解决这类“最长连续子区间”问题，滑动窗口 是一种非常高效和直观的算法模型。

解题思路

我们可以设想有一个“窗口”在 fruits 数组上滑动。这个窗口代表了我们正在连续采摘的水果序列。算法的目标就是找到这个窗口在满足“最多两种水果”的条件下，所能达到的最大宽度。

实现这个思路，需要以下几个关键部分：

定义窗口边界
- 需要两个指针，一个左指针 left 和一个右指针 right，它们共同构成了当前的窗口 [left, right]。
跟踪窗口状态
- 为了判断窗口内的水果是否超过两种，需要一个数据结构来实时统计窗口内每种水果的数量。通常使用 哈希表 (HashMap) 或频率数组来实现，我们称之为 counts。
- counts 的键（key）是水果的种类，值（value）是该水果在当前窗口中出现的次数。
窗口的移动逻辑 算法的核心在于窗口如何移动，这包含“扩张”和“收缩”两个过程：a. 扩张窗口b. 收缩窗口
- 让右指针 right 不断向右移动，把新的水果 fruits[right] “装入”窗口。
- 每装入一个新水果，就在 counts 中更新它的数量。
- 此时，窗口的长度增加。我们可以用当前窗口的长度去更新记录到的最大长度。

在扩张过程中，一旦发现 counts 中不同水果的种类（即哈希表中键的数量）超过了 2，说明当前窗口不再满足条件，必须进行收缩。
收缩是通过移动左指针 left 来实现的。将 fruits[left] 从窗口中“丢弃”。
每丢弃一个水果，就在 counts 中将它的数量减 1。
关键点：如果某个水果在 counts 中的数量减为 0，意味着这种水果已经完全被移出窗口，此时需要从 counts 中移除这个键。
持续收缩（即 left 指针不断右移），直到 counts 中的水果种类重新变回 2 种为止。这时，窗口再次变得有效。

具体步骤

初始化：
- 左指针 left = 0，右指针 right = 0。
- 初始化一个空的哈希表 counts 用于计数。
- 初始化一个结果变量 maxLength = 0 用于存储最大长度。
主循环：
- 右指针 right 从左到右遍历整个 fruits 数组。
- 在每一步，将 fruits[right] 加入窗口，并更新 counts。
判断与收缩：
- 检查条件：当 counts 中的水果种类数量大于 2 时：
  - 从窗口左侧移除水果 fruits[left]，并更新 counts。
  - 将左指针 left 向右移动一位。
  - 重复此过程，直到 counts 中的水果种类数量降至 2。
更新结果：
- 在每次窗口扩张后（且窗口有效时），计算当前窗口的长度 right - left + 1。
- 用这个长度更新 maxLength：maxLength = max(maxLength, right - left + 1)。
返回结果：
- 当 right 指针遍历完整个数组后，maxLength 中存储的就是最终的答案。

具体代码

实现有些许不同：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {

        int rightPos = 0; // 滑动窗口的右边界指针
        int leftPos = 0;  // 滑动窗口的左边界指针
        int variety = 0;  // 记录当前窗口内水果的种类数

        int result = 0;   // 存储最终结果，即满足条件的最大水果数
        int n = fruits.size(); // 数组长度，用于循环边界判断
        // 使用一个频率数组来模拟哈希表，统计窗口内每种水果的数量。
        // 题目约束了 fruits[i] < n，所以可以用数组直接映射。
        vector<int> countmap(n, 0); 

        // 右指针遍历整个数组，以扩张窗口
        while(rightPos < n)
        {
            // --- 情况一：窗口可以扩张 ---
            // 条件：当前水果已在篮子中，或者篮子还没满（种类数小于2）
            if(countmap[fruits[rightPos]] != 0 || (countmap[fruits[rightPos]] == 0 && variety < 2))
            {
                // 如果是新品种的水果，种类数加1
                if(countmap[fruits[rightPos]] == 0) {
                    variety++;
                }
                
                // 将当前水果计入频率图，并移动右指针
                countmap[fruits[rightPos]]++;
                rightPos++;
                
                // 更新最大水果数。当前窗口的长度为 rightPos - leftPos
                result = max(result, rightPos - leftPos);
            }
            
            // --- 情况二：窗口必须收缩 ---
            // 条件：遇到了第三种不同的水果
            else
            {
                // 持续收缩窗口，直到腾出一个篮子（种类数变回1）
                // 注意：这里的循环条件写 variety == 2 也可以，因为进入 else 分支时 variety 必为 2
                while(variety == 2)
                {
                    // 从窗口左边移除水果
                    countmap[fruits[leftPos]]--;
                    
                    // 如果移除后，该水果数量变为0，说明一个种类被完全移除，种类数减1
                    if(countmap[fruits[leftPos]] == 0) {
                        variety--;
                    }
                    
                    // 左指针右移，收缩窗口
                    leftPos++;
                }
            }
        }
        
        return result; // 返回记录的最大值
    }
};

904. 水果成篮

beautifulremi

题目

解题思路

题意分析

解题思路

具体步骤

具体代码