题目描述

滑动窗口，维护一个双向队列dq，分为以下几种情况，用下面的样例[100, 3, 2, 1, 5, 1, 1, 1] , k=3说明。
1 窗口里面的元素小于3，往dq加元素
2 已经输入了100 3 2，下一轮输入1，虽然100很大很好，但是已经超出了滑动窗口的范围，只能丢掉，把3当成最大，队列里面有3 2 1
3 再下一轮输入的数字是5，此时先pop了3，因为他已经超出了滑动窗口的范围。队列里面有2 1，它们已经派不上用场了，因为新来的5，不仅比他们大，而且是最新来的，是当前最慢超出滑动窗口范围的，又大又耐用，2和1比5小且没5耐用，直接pop掉。
4 注意队列里面放的是下标，这样子方便计算有没有超出滑动窗口的范围，而返回的答案放的是数值

样例

输入：[100, 3, 2, 1, 5, 1, 1, 1] , k=3

输出: [100, 3, 5, 5, 5, 1]

算法1

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> dq;
        for (int i = 0; i < nums.size(); i++) {
            if (dq.size() && dq.front() < i - k + 1) dq.pop_front();//这个头部虽然很大，但是已经超出了窗口的范围，只能pop掉
            while (dq.size() && nums[dq.back()] <= nums[i]) dq.pop_back();//处理尾部，新来的比尾部大，那么尾部都可以pop掉，因为新来的大，且是这轮迭代中最慢超出滑动窗口范围的，所以前面的小于等于它的都没用了
            dq.push_back(i);//新来的入队
            if (i >= k - 1) ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};