题解 | #滑动窗口的最大值#

#include <deque>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        
        // write code here
        deque<int> q;
        vector<int> res;

        if(size==0 || size>num.size()) return  res;
        for(int i=0;i<num.size();i++){
            // 保证序列单调递减。
            //2 ；   2，3；   4；   4，2；    6；    6，2；    6，5 ；   5，1；
            while(!q.empty() && num[q.back()]<num[i]) q.pop_back();
            //入队列
            q.push_back(i);
            //出队列
            if(i-q.front()>=size){
                q.pop_front();
            }

            //答案
            if(i +1 >= size){
                res.push_back(num[q.front()]);
            }

        }
        return res;
        

    }
};

这个题目很有意思，重点就是我到底应该如何设计这个 前后的队列

因为我不可能只维护当前最大的值

当最大值出了之后，它后面的一部分值都没了，又得重新便利

所以我必须维护这个队列，队列单调递减，且每次进入循环，

1.让队尾小于当前的都出来，只要自己进去就行（维护单调性）

2.让队列最前面，（不在窗口）超出的部分退出， --》这个是一开始最没想明白的

当i〉size时 就可以把列表头的答案作为答案了