problem:904. 水果成篮

思路:滑动窗口维护窗口内的水果种类数。

Accode:

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int ans = 0;
        int len = fruits.size();
        vector<int> cnt(len,0);
        int total = 0;
        int sum = 0;
        deque<int> deq;
        for(int i=0;i<len;i++){
            while(deq.size() && total>=2 && cnt[fruits[i]]==0){
                int front = deq.front();
                cnt[fruits[front]]--;
                if(cnt[fruits[front]]==0) total--;
                deq.pop_front();
            }
            deq.push_back(i);
            cnt[fruits[i]]++;
            if(cnt[fruits[i]]==1) total++;
            ans = max(ans,i-deq.front()+1);
        }
        return ans;
    }
};

时间复杂度：$o(n)$