当前位置：首页 > article >正文

[Day 12]904.水果成篮

article 2025/1/7 9:56:33

今天给带来的题目是滑动窗口的另一种题目，之前我们讲了滑动窗口题目中长度最小的子数组，今天这个题目实际上是求长度最长的子数组
题目描述：力扣链接 904.水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

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

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

示例：

输入：fruits = [1,2,3,2,2]
输出：4

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

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5

解释：可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length
这道题我刚开始看的时候就感觉读不懂题，这个题目描述的晕晕乎乎的，一个树上怎末能有两种类型果子？不过题还是要做的，我通过搜了·多种解释才理解了原来这个题目想告诉我们有一个整数数组fruits，我们从头遍历它**找到只能有两种类型的元素（就是只能有两个数字相同），然后找出最长的连续数组返回长度。**那么思路如下:

思路

本道题是滑动窗口的类型，也是双指针法的一种，因为题目是两个类型的元素，我们要用哈希表unoredered_map<int,int>来定义这个数组。因为它可以遍历出两个不同类型的元素出来，哈希表的size(),erase(),为键值对，搭配使用就是key-value，key是树的种类，value是树的数量。
1.首先我们初始化变量left,right用来进行循环遍历，因为窗口会向右移动，我们将右边用来扩大窗口，左边用来缩小窗口。
2.初始化一个max_fruits=0，用来比较更新后面最大长度的大小，然后我们进行for循环开始扩大窗口，就是把fruit_type[fruits[right]]++。
3.当元素种类大于2的时候，从最左边移动窗口，直到种类数量回到2以内，就是把left++，同时最左边的数数量-1，防止被加到后面元素，当左边的的数量被减到0时，说明窗口内已经没以后这种水果了，就用后面的if语句从哈希表中删除，表明后面的元素种类会减小。
4.最后，我们通过right-left+1获得数组长度，通过组组比较更新最大值，我们最后将最大值返回。
在这里插入图片描述
我们以这个数组为例fruits = [3,3,3,**1,2,1,1,2,**3,3,4]，首先，从头遍历这个数组，找的是依次遍历数组后，只有两个类型元素的连续子数组，并且长度是最长，想这个数组，从3开始，一直到3331为满足题意的一个子数组，长度为4。然后继续向后遍历到结束，下一组为12112，长度为5。下一组233，长度为3，下一组34，长度为2。显而易见，12112是只有两个元素且长度最长的，所以我们返回长度5。

完整代码如下:

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left=0;//初始化左边为0
        int max_fruits=0;//初始化最大值为0
        unordered_map<int,int>fruits_type;//用哈希map来存储数组（一个是种类，一个是数量）
        for(int right=0;right<fruits.size();right++){
            fruits_type[fruits[right]]++;//扩大窗口，将右边向后移动遍历
            while(fruits_type.size()>2){//直到数组元素（种类）大于2时
                fruits_type[fruits[left]]--;//缩小窗口，每移动一次左边界，种类的数量-1，直到元素内只剩两个元素
                if(fruits_type[fruits[left]]==0)//减到0时
                {
                    fruits_type.erase(fruits[left]);//这个种类已经完全移除窗口了，从哈希表中删除
                }
                left++;//缩小窗口
            }
            max_fruits=max(max_fruits,right-left+1);//比较更新最大长度（数目）
        }
        return max_fruits;//返回你可以收集的水果的 最大 数目。
    }
};