LeetCode904. 水果成篮

904. 水果成篮（学到新方法会更新）

一、题目

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

（1）你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
（2）你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
（3）一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
1
2
3
4

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

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

示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
1
2
3
4

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fruit-into-baskets
著作权归领扣网络所有。

二、解法

方法一：三指针+类似滑动窗口

一、读题

（1）看题目，找到一个不符合的就停下，比如1、2、3、2、2，比如前两个1和2类水果均放到篮子里，那么到3就必须停下，因此可以看出，我们找的就是一个子数组，这个子数组中只有两类水果，数组的长度越长越好。

二、思路

建立三个指针，left\middle\right（初始值均为0，代表数组下标）；分工如下：left和middle代表相邻两种水果（有可能是同一种）（比如1、1、2、1、2、3，1和2就是相邻两种不同水果，1和1也可以算，后面就知道为什么了），right是去寻找新的一种，当寻找到的时候，left和middle各自往后移动一种（right遇到3，那么left和middle分别变成2、3）。
具体操作：
（1）right等于left或者是middle的时候，一直向右移动，如果不等于left和middle的话说明right遇到了left和middle外的第三类水果（如果left和middle相等就是第二类水果），就先停下。
（2）遇到第三类水果的时候，分为两种情况，第一种是1、1、2、1、2、2、3、3，遍历到2的时候right就相当于遇到了第二类水果（不同于left和middle），此时让left=middle=0，middle=right=2，记录下新水果的类别，然后right继续向后遍历；第二种情况是第一种情况发生以后right继续遍历，当到3的时候，遇到了1和2以外的不同的数字（遇到了第三种水果），如果这时候和前面一样，left=middle=2，right=middle=6，那么我们会发现left\middle\left~middle之间会有三种水果，就不符合我们的设定了（left和middle是相邻的两种不同水果），因此我们先将middle设置成为新水果3，然后将left设置成为新水果3的前面一位，也就是fruits[5]，向前遍历到不等于fruit[5]为止，然后向后再加一位重新等于fruit[5]，这样就记录下了符合要求的left。
（3）什么时候得到max？当right找到新的值以后，就记录下right-left，然后找到更大的，就记录下更大的（详情见代码）。

三、代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0, right = 0, middle = 0;
        int max = 0;
        bool flag = 1;
        //移动right指针
        while (right < fruits.size()) {
            //right等于left或者是middle的时候，一直向右移动
            while (right < fruits.size() && (fruits[right] == fruits[left] || fruits[right] == fruits[middle])) {
                //出现第二种情况
                if (fruits[right] == fruits[left] && fruits[right] != fruits[middle]) flag = 0;
                right++;
            }
            //更新max
            max = (right - left) > max ? (right - left) : max;
            //第二种情况
            if (flag == 0) {
                middle = right;
                left = middle - 1;
                while (fruits[left] == fruits[middle - 1]) {
                    left--;
                }
                left++;
            }
            //第一种情况
            else {
                left = middle;
                middle = right;
            }
        }
        return max;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

方法二：滑动窗口

一、思路

定义四个指针
j 负责遍历fruits数组；
f1 为第一种水果类型的起始索引，即第一个篮子的起始索引；
f2 为第二种水果类型的起始索引，即第二个篮子的起始索引；
t 为未来两个篮子里的第一个篮子的起始索引。
滑动窗口的左边界为 f1，右边界为 j。

更新 j
通过for循环使 j 从 0 遍历到 fruits.size()-1 。

更新 f1
f1 初始为0，当遍历到第三种水果类型时，若 f1!=f2，则更新f1 为 t，即f1=t，保证计算子序列长度时只有两种水果类型。

更新 f2
f2 初始为0，当遍历到第二种水果类型或第三种水果类型时，则更新 f2 为 j，即f2=j，保证计算子序列长度时只有两种水果类型。

更新 t
t 初始为0，每次 t 与当前的 j 作对比，当 fruits[t]!=fruits[j]时，更新 t 为 j，即 t=j，作为未来两个篮子里的第一个篮子的起始索引。
C++版本：

```cpp
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //当fruits数组长度≤2，则直接返回fruits数组长度
        if(fruits.size()<3) return fruits.size();
//mn为结果，即fruits数组中包含两个不同水果类型的最大子序列长度
        int mn=0;
/*j为遍历fruits数组的指针，也是滑动窗口的右边界，f1,f2分别为第一个和第二个篮子
的起始索引，f1同时也是滑动窗口的左边界，t为未来两个篮子里的第一个篮子的起始索
引*/
        for(int j=0,f1=0,f2=0,t=0;j<fruits.size();j++)
        {
/*当f1=f2时，fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明遇到的是第二个篮子
要装的第二种水果；当f1!=f2时，fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明
遇到的是第三种水果*/
            if(fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2])
            {
/*当f1=f2时，说明第一个篮子已经装了一种水果，第二个篮子里还没有装，不更新f1，
只更新f2，即往第二个篮子里装第二种水果；
当f1!=f2时，fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明遇到的是第三种水果，
则更新f1和f2，即当前两个篮子的两种水果已装满，更新f1和f2为未来两个篮子里的两种
水果*/
                if(f1!=f2) f1=t;
                f2=j;
            }
/*t寻找未来两个篮子中第一个篮子要装的一种水果的起始索引，每次t与当前的j作对比，
当fruits[t]!=fruits[j]时，更新t=j*/
            if(fruits[t]!=fruits[j]) t=j;
/*更新当前子序列的长度，即每次计算装入两个篮子中的水果总数目*/
            mn=mn>(j-f1+1)?mn:(j-f1+1);
        }
        return mn;//返回最终结果mn
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if(fruits.size()<3) return fruits.size();
        int mn=0;
        for(int j=0,f1=0,f2=0,t=0;j<fruits.size();j++){
            if(fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]){
                if(f1!=f2) f1=t;
                f2=j;
            }
            if(fruits[t]!=fruits[j]) t=j;
            mn=mn>(j-f1+1)?mn:(j-f1+1);
        }
        return mn;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

作者：Linken_54
链接：https://leetcode.cn/problems/fruit-into-baskets/solution/by-0xula58rcn-umun/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。