自己第一次写的,结果超时了
class Solution
{
public:
int totalFruit(vector<int> &fruits)
{
int r = 1;
int res = 1;
while (r < fruits.size())
{
int l = r - 1;
int n = 1; // 代表不同的种类个数
int second = -1;
while (n <= 2 && l >= 0)
{
if (fruits[l] == fruits[r] || fruits[l] == second)
l--;
else
{
n++;
if (n <= 2)
{
second = fruits[l]; // 记录第二个种类,第一个种类其实是fruits[r]
l--;
}
}
}
res = max(res, r - l);
r++;
}
return res;
}
};
我的思想中为什么要让l--
放在if (n <= 2)
里面而不是外面?
因为我想的是让当r固定时,r最后指向的是从r往左走第一个不满足条件的位置(即不满足水果种类数不超过两种),然后计算的长度就是r-l
。
其实在写的时候就隐隐感觉会超时,因为l肯定不应该从r-1
开始回溯,但是又想不到别的方法(其实想到了应该要用滑动窗口,但是具体的细节没想清楚,不知道如何下手)。
看了官方题解,果然是滑动窗口
代码如下:
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;
}
};
这个滑动窗口维持的性质:这个窗口内的水果种类不超过两种。
标签:水果,right,904,int,cnt,成蓝,++,second,fruits From: https://www.cnblogs.com/hisun9/p/18540603