904.水果成篮

目录 一、题目二、思路2.1 解题思路2.2 代码尝试2.3 疑难问题 三、解法四、收获4.1 心得4.2 举一反三

一、题目

二、思路 2.1 解题思路 2.2 代码尝试 #include <map> class Solution { public: int totalFruit(vector<int>& fruits) { std::map<int, int> pla; int l=0,r=0; int cur=0;//统计当前收集的水果数目 int ret=0;//统计采摘的最大数目 //开始采集，先按当前的第一个采集，统计窗口内采集情况 while(r<fruits.size()){ //窗口内每次遍历一个值，就把他加入哈希表，并维护哈希表 pla[fruits[r]]++; //如果哈希表的长度大于2，说明需要把l键删除 if(pla.size()<=2){ cur++; ret=max(cur,ret); }else{ cur--; pla.erase(fruits[l]); l++; r++; ret=max(cur,ret); } //判断如果哈希表长度超出2或者篮子数目不够了 } //如果当前窗口不满足，限制了右指针的发展，那就更新左指针，然后再在此基础上继续更新右指针滑动窗口 return ret; } };

想用哈希表来维护滑动窗口中的数据

2.3 疑难问题 三、解法 class Solution { public: int totalFruit(vector<int>& fruits) { int n = fruits.size(); unordered_map<int, int> cnt; int left = 0, ans = 0; for (int right = 0; right < n; ++right) { ++cnt[fruits[right]]; while (cnt.size() > 2) { auto it = cnt.find(fruits[left]); --it->second; if (it->second == 0) { cnt.erase(it); } ++left; } ans = max(ans, right - left + 1); } return ans; } }; 作者：力扣官方题解 链接： leetcode /problems/fruit-into-baskets/solutions/1893352/shui-guo-cheng-lan-by-leetcode-solution-1uyu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 四、收获 4.1 心得

感觉思路已经很接近了，但是哈希表那边的写法有点忘记，另外逻辑思路也有点并不是很清晰。滑动窗口的里面那个收敛的判断条件应该是如何收敛左边边界，判断条件是不满足窗口

4.2 举一反三

分治去思考解题很有帮助