Leetcode——904. 水果成篮
概述
-
题目有点啰嗦,主要注意第二个规则
分析
-
根据规则2,我们可以知道,一旦选择了一颗果树开始,则后面连续出现的果树被必须采摘,实际上就是一个求满足条件的连续子数组问题 因此,我们根据之前的分析总结,考虑采用滑动窗口解决该问题
思路
双指针实现滑动窗口思路?
-
见代码部分
代码
class Solution { public: int totalFruit(vector<int>& fruits) { int result = -1; // 记录result unordered_map<int,int> kind; // 最大是2,所以空间O(1) int windows_begin = 0, windows_end = 0; for(; windows_end < fruits.size(); ++windows_end) { ++kind[fruits[windows_end]]; // 某个类型的水果数+1 if (kind.size() == 3) { // 窗口内水果类型==3,刚好不合法,此时记录数据 result = max(result, windows_end - windows_begin); // 记录结果,不需要+1,因为fruits[windows_end]是不应该加入窗口的元素 while (--kind[fruits[windows_begin++]] != 0) ; // 窗口左边界移动,判断移出动作是否导致窗口内水果种类减1 kind.erase(fruits[windows_begin - 1]); // 删除该水果类型 } } // 额外处理,因为我们记录结果的时候,要求kind.size()==3,才记录(当然,可以将result移动 //但是windows_end移动到数组结尾,窗口记录可能并没有=3,所以需要额外记录比较一下 return windows_end - windows_begin > result ? windows_end - windows_begin : result; } };
考虑
- 如何记录窗口中新加入的元素? 因为题目中对窗口不合法的限制是根据水果的类型,所以我们应该需要记录的是窗口保存水果的类型
- 如何判断窗口不合法? 题目要求窗口内的水果类型不超过2,所以当当前窗口内的水果类型=3时,则判断窗口不合法了,也就不需要继续移动窗口右边界
- 如何在移动窗口左边界时,判断移动后的窗口是否合法 因为左侧移动窗口左边界时,会将一个水果移出,该水果有一个类型 当窗口合法时,应该是因为该水果移出,导致窗口内的水果种类刚好减1 (因为我们开始移动左边界时的水果类型是3) 但是,注意的是,一个类型可能有多个水果,移出某个水果,并不代表将该种类的水果全部移出,所以我们应该需要记录窗口中某个种类的水果的数量,据该种类移除的水果的数量来判断来判断
综上,我们需要记录窗口的水果类型和每个类型拥有的水果数,所以我们考虑使用unordered_map:
-
key保存水果种类,value保证该类型的水果数 而判断水果类型是否==3,map也有内置函数size()