滑动窗口的最大值 O(N)时间复杂度

维护一个窗口和一个双端队列
窗口的左端点为L，右端点为i，一开始L和i都是0，让i从0开始滑动，在此期间维护一个双端队列qmax
i向右移动，代表往窗口中加入数据：
如果nums[i] < qmax的尾部数据，则i这个下标直接从尾部进入双端队列
如果nums[i] > qmax的尾部数据，则qmax的尾部一直出队，知道队为空或者队尾小于nums[i]

deque<int> qmax; // 最大值双端队列，保存的是下标
        int L = 0; // 窗口左端点
        for(int i = 0;i<num.size();i++){
            while(!qmax.empty() && num[qmax.back()] <= num[i]){
                qmax.pop_back();
            }

当形成长度为size的窗口时，L开始移动，代表从窗口中删除数据：
对比L-1与qmax的队头，如果相等，则队头出队（表示这个数已经被剔除了）

if( i >= size - 1){//如果形成了窗口
                ans.push_back(num[qmax.front()]);
                L ++;
                if(qmax.front() == L-1){
                    qmax.pop_front();
                }
            }

完整代码：

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ans;
        if(num.empty() || size < 1 || num.size() < size){
            return ans;
        }
        deque<int> qmax; // 最大值双端队列，保存的是下标
        int L = 0; // 窗口左端点
        for(int i = 0;i<num.size();i++){
            while(!qmax.empty() && num[qmax.back()] <= num[i]){
                qmax.pop_back();
            }
            qmax.push_back(i);

            if( i >= size - 1){//如果形成了窗口
                ans.push_back(num[qmax.front()]);
                L ++;
                if(qmax.front() == L-1){
                    qmax.pop_front();
                }
            }
        }
        return ans;

    }
};

整个过程就是将窗口的右端点一直推到数组的最后一个位置，所以时间复杂度是o（n）