单调队列

⌈单调栈⌋主要解决 Next Greater Number 一类问题，而⌈单调队列⌋这个数据结构可以解决滑动窗口相关的问题。

输入一个数组 nums 和一个正整数 k，有一个大小为 k 的窗口 nums 上从左至右滑动，输入每次窗口中 k 个元素的最大值。

01 滑动窗口最大值

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

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

  1. 示例 1：
  3. 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
  4. 输出：[3,3,5,5,6,7]
  5. 解释：
  6. 滑动窗口的位置                最大值
  7. ---------------               -----
  8. [1  3  -1] -3  5  3  6  7       3
  9.  1 [3  -1  -3] 5  3  6  7       3
  10.  1  3 [-1  -3  5] 3  6  7       5
  11.  1  3  -1 [-3  5  3] 6  7       5
  12.  1  3  -1  -3 [5  3  6] 7       6
  13.  1  3  -1  -3  5 [3  6  7]      7
  14. 示例 2：
  16. 输入：nums = [1], k = 1
  17. 输出：[1]
  18. 示例 3：
  20. 输入：nums = [1,-1], k = 1
  21. 输出：[1,-1]
  22. 示例 4：
  24. 输入：nums = [9,11], k = 2
  25. 输出：[11]
  26. 示例 5：
  28. 输入：nums = [4,-2], k = 2
  29. 输出：[4]
  32. 提示：
  34. 1 <= nums.length <= 105
  35. -104 <= nums[i] <= 104
  36. 1 <= k <= nums.length
  38. 来源：力扣（LeetCode）
  39. 链接：https://leetcode-cn.com/problems/sliding-window-maximum
  40. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

⌈窗口⌋是不断滑动的，需要动态地计算窗口中的最大值。每个窗口前进的时候，要添加一个数同时减少一个数。

一个普通队列一般有这两个操作：

class Queue {
    // 在队尾加入元素 n
    void push(int n);
    // dequeue 操作，删除对头元素
    void pop();
};

单调队列的操作类似：

class MonotonicQueue {
    deque<int> que;
    // 在队尾添加元素 n
    void push(int n) {
        while (!que.empty() && n > que.back()) {
            que.pop_back();
        }
        que.push_back(n);
    }
    // 返回当前队列中的最大值
    int max() {
        // 按照 push 规则,对列头部就是最大值
        return que.front();
    }
    // 队头元素如果是 n，删除
    void pop(int n) {
        // 在向前移动窗口时，先缩小窗口，在扩大窗口
        if (!que.empty() && n == que.front())
            // 如果窗口最左侧元素没有被删除，则要删除。因为他可是最大值，一直保存在单调队列中
            que.pop_front();
    }
};

⌈滑动窗口⌋问题的框架如下：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MonotonicQueue que;
    vector<int> res;
    for (int i = 0; i < k; ++i)
        que.push(nums[i]);
    res.push_back(que.max());
    for (int i = k; i < nums.size(); ++i) {
        que.pop(nums[i - k]);
        que.push(nums[i]);
        res.push_back(que.max());
    }
    return res;
}