【算法|滑动窗口No.2】leetcode904. 水果成篮

小鱼儿 2024-04-27 06:47 117阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][2c60c22bffc444ada97d6b08add5486f.png]

[点击直接跳转到该题目][Link 3]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣算法分析
 *  3️⃣代码编写

## 1️⃣题目描述 ##

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 `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 <=  1 0 5 10^\{5\} 105
 *  `0 <= fruits[i] < fruits.length`

## 2️⃣算法分析 ##

本题利用滑动窗口的思想，通过维护一个窗口，保证窗口中水果种类的数量不超过2个。每次遇到第3个不同种类的水果时，通过移动窗口左边界来调整窗口中的水果种类数量。

*  每次遇到一个新的水果，将其计数加一，如果计数变为1，表示遇到了一种新的水果，水果种类数量增加一。
 *  如果水果种类数量超过了2，需要调整窗口。
 *  每次调整窗口后，更新结果 ret 为当前窗口的长度和历史最大值的较大值。

## 3️⃣代码编写 ##

class Solution {
        
    public:
        int totalFruit(vector<int>& fruits) {
        
            unordered_map<int,int> count;
            int ret = INT_MIN;
            for(int i = 0,j = 0,s = 0;i < fruits.size();i++)
            {
        
                if(++count[fruits[i]] == 1) s++;
                while(s > 2) 
                {
        
                    if(--count[fruits[j]] == 0) s--;
                    j++;
                }
                ret = max(ret,i - j + 1);
            }
            return ret;
        }
    };

**最后就同通过啦！！！**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[2c60c22bffc444ada97d6b08add5486f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/0b9269f58eff47b1916e2805dc214f8b.png
[Link 3]: https://leetcode.cn/problems/fruit-into-baskets/description/