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

#include <deque>
#include <queue>
#include <vector>
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        deque<int> q;
        vector<int> res;
        for(int i = 0;i<num.size();++i)
        {
            //如果队头元素的下标与当前i的距离超过了size，说明该元素不在滑动窗口内了，要删除
            while(!q.empty() && i-q.front()+1 >size)
            {
                q.pop_front();
            }
            //如果新的元素比队列的尾元素大，则该尾元素不可能为该滑动窗口的最大值，所以将队列后面比新的元素小的元素全部弹出，之后再加入新的元素，队列中剩下的元素严格单调递减
            //例如8 6 4 ，加入5，就需要弹出4，此时为8 6 5，严格递减
            while(!q.empty() && num[q.back()] <= num[i])
            {
                q.pop_back();
            }
            q.push_back(i);//将新的元素压入队列
            //当前遍历的长度大于等于窗口窗口长度才开始存储答案
            if(size && i>= size -1)
                res.push_back(num[q.front()]);
        }
        return res;
    }
};

思路：使用单调队列

单调队列是一种高效处理求滑动窗口最值的数据结构，其本身是一个双端队列(deque)，其可以通过O(n)的线性时间复杂度求出最值

原理：如果队列中存在两个元素，满足 a[i] >= a[j] 且 i < j，那么a[j]将不可能作为窗口中的最大值，此时可以直接将 a[j] 删掉；通过这样的操作队列中剩下的元素严格单调递减，故队头就是整个队列中的最大值，求窗口的最值也可以直接通过O(1)的复杂度访寻。

而维护出这种队列的方法只需要我们在往队尾插入元素之前，先将队尾小于等于当前数的元素全部弹出即可