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

方法：双向队列

双向队列就是一种特殊的队列，双向队列两边，即头部和尾部都可以进行插入元素和删除元素的操作，但是也只能插入到最尾部或者最头部，每次也只能取出头部元素或者尾部元素后才能取出里面的元素。

具体做法：

• step 1：维护一个双向队列，用来存储数列的下标。
• step 2：首先检查窗口大小与数组大小。
• step 3：先遍历第一个窗口，如果即将进入队列的下标的值大于队列后方的值，依次将小于的值拿出来去掉，再加入，保证 队列是递增序。
• step 4：遍历后续窗口，每次取出队首就是最大值，如果某个下标已经过了窗口，则从队列前方将其弹出。
• step 5：对于之后的窗口，重复step 3，直到数组结束。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        vector<int> res;
        //特殊情况处理
        if (size > num.size() || size == 0)
            return res;

        deque<int> temp;
        //遍历第一个窗口
        for (int i = 0; i < size; i++) {
            //去掉比自己先进入队列的小于自己的值
            while(!temp.empty() && num[i] > num[temp.front()])
                temp.pop_back();
            temp.push_back(i);
        }

        for (int i = size; i < num.size(); i++) {
            //每移动一位，将窗口最大值推入数组
            res.push_back(num[temp.front()]);
            //当滑动窗口移动到超出队列头元素时，弹出队列头元素
            while (!temp.empty() && temp.front() < i - size + 1)
                temp.pop_front();
            //每移动一次，将前面小于当前值的序列全部弹出
            while (!temp.empty() && num[i] > num[temp.back()])
                temp.pop_back();

            temp.push_back(i);
        }
        //将最后一个滑动窗口的最大值推入数组
        res.push_back(num[temp.front()]);

        return res;
    }
};