239. 滑动窗口的最大值

单调队列的模板题，但是我一直记不住😢。

题目描述如下：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

输入输出示例及数据范围：

思路

下面所给的思路不是单调队列的分析思路，而是如何使用单调队列来解决这道题目的思路。

单调队列顾名思义，队列当中的数据可以按照某种顺序形成单调性，比如从队头到队尾数据是单调递减的。解决这道题目正是利用到了这一条性质，即队列当中元素按照整型数据的大小递减。

我们需要维护一个双端队列（比如 C++ 当中的 deque），双端队列当中存储的值是原数组的下标，存储下标的好处有两点，第一点就是可以直接通过下标索引原数组得到数据的值，第二点是可以判断当前下标是否超出了滑动窗口的范围，如果超出了就把这条数据踢出去。

现在我们开始对数组进行遍历。首先对于一个新来的数据，为了维持单调队列的有序性，我们需要不断地判断当前元素和队尾元素谁大谁小，如果队尾下标对应的元素不比当前元素大，那么此时将当前元素插入到队尾不能保持单调队列的单调性，遂将当前的队尾踢出队列（直接 pop_back）。不断地进行比较直到当前队尾下标索引到的数据比当前数据要大，将当前数据的下标排在队尾即可，或是队列被清空（意味着当前队列中所有的数据都不比当前元素更大，为了维护双端队列的单调性，当前元素被作为队首元素【即最大值】插入到了队列当中）。

插入元素之后，现在我们开始维护本题所使用的单调队列的第二条性质，即队列当中的元素不能是过期的（即：队列当中的元素应该在滑动窗口的范围内）。维护这条性质非常的简单，只需要不断地查看队首元素（还记得嘛？队列当中存储的是下标）与当前下标的差值是否大于滑动窗口的大小 k 即可。如果队首的元素过期，那么将队首的元素踢出即可（直接 pop_front）。

维护好双端队列之后，现在我们可以将当前元素的下标插入到队尾（push_back）。此时该元素插入的位置一定是合法的。

最后保存答案，只有当当前遍历的下标$i\ge k-1$ 的时候，队首元素（是下标）索引到的值才能加入到答案当中，因为此时单调队列的长度恰好与滑动窗口一致。

C++ 实现

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;

        int n = nums.size();
        for(int i=0; i<n; i++) {
            while(dq.size() && nums[dq.back()] < nums[i])   dq.pop_back();
            while(dq.size() && i - dq.front() >= k)         dq.pop_front();
            dq.push_back(i);
            if(i >= k - 1) {
                ans.push_back(nums[dq.front()]);
            }
        }

        return ans;
    }
};