滑动窗口的最大值【C++解题反思】

#include <deque>
#include <queue>
#include <vector>
class Solution {
public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        vector<int>res;
        deque<int>dq;
        if(num.size()>=size && size!=0){
            for(int i=0; i<num.size(); i++)
            {
                while(!dq.empty() && dq.front()<i-size+1) 
                    dq.pop_front();
                while(!dq.empty() && num[dq.back()]<num[i])
                {
                    dq.pop_back();
                }
                dq.push_back(i);
                if(i<size-1) continue;
                res.push_back(num[dq.front()]); 
            }
        }
        return res;
    }
};

双向队列的精髓在于双向操作（废话），因此可以有效应对需要根据两个条件分别进行操作的情况。

队列中不一定要存数组中的值，也可以存数组的下标，然后再通过num[dq.front()]等来访问数组中的值。这一点在涉及到处理“窗口向后移动，前面的值要丢弃”这一要求上非常重要。

滑动窗口性质总结【笔者乱编的】：

两元素性：每次向后滑动一位，进来一个，出去一个，这两个元素是重点关注对象，内部的都没改变。

前无关性：如果新的元素比旧的元素大，那这个旧的元素未来也一定不是最大的，根据题目所求可以直接舍去。