LeetCode 904.水果成篮
思路🧐:
求水果的最大数目,也就是求最大长度,我们是单调的向前求解,则能够想到使用滑动窗口进行解答,可以用hash表统计每个种类的个数,kinds变量统计当前种类,left和right表示左边框和右边框,且都从起点开始。
右边框先走,当种类个数为0时,表示这是个新种类,kinds++,当kinds大于2,则不满足题意,需要删减旧的种类,再移动左边框,当种类个数为0时,旧种类删减完成,继续移动右边框,重复该过程并每次循环都算一下长度,直到right走到尾结束。
代码🔎:
class Solution { public:int totalFruit(vector<int>& fruits) {int hash[100001] = { 0 }; //针对题目数据范围优化int len = 0;for(int left = 0, right = 0, kinds = 0; right < fruits.size(); right++){if(hash[fruits[right]] == 0) //如果哈希表对应的水果下标为0,就表示有一个新的种类kinds++;hash[fruits[right]]++; //对应下标修改个数while(kinds > 2) //当种类大于2,表示不能再装了,需要消除旧的种类{hash[fruits[left]]--; //对应hash表减去该种类个数if(hash[fruits[left]] == 0) //当减到0,表示旧的种类没有了kinds--; //种类减少left++; //移动左边框}len = max(len, right - left + 1); //长度计算}return len;} };
return len;
}
};
![image-20241124191735745](https://img-blog.csdnimg.cn/img_convert/6b419397b927e6f34c470b60ba8ea3fd.png)