Monotonic Queue

Monotonic Queue 是一种主要用于解决 滑动窗口类问题 的数据结构，在长度为 n 的序列中，求每个长度为 k 的区间的区间最值，它的时间复杂度是 O(n) 的。

Monotonic Queue 的基本思想是维护一个 VecDeque，遍历序列，当且仅当一个元素可能成为最值时才存储他：以单调增为例，因为左边的元素总是先于右侧的元素离开，所以

• 如果右侧新来的元素 curr 大于其左侧的元素，则所有其左边的更小的元素在后续的滑动中都没有机会成为最大的元素，所以将全部被弹出后压入 curr
• 如果右侧新来的元素 curr 小于等于其左侧的元素，但是如果再之后滑入的元素有着更小的值的话，在 curr 左侧所有元素滑出后，curr 依然有机会成为窗口内的最值，所以压入 curr

其满足性质从左到右的所有元素是单调的，首元素记录了最值。

---

以 239. Sliding Window Maximum 为例，我们维护一个 VecDeque 用于记录当前窗口中所有在移动后可能成为最值的所有元素。

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3`
|----------------------------------------------|
| array                      | monotonic queue |
|----------------------------------------------|
| [1 3  -1] -3  5  3  6  7  | [3, -1]          |
| 1 [3  -1  -3] 5  3  6  7   | [3, -1, -3]     |
| 1  3 [-1  -3  5] 3  6  7   | [5]             |
| 1  3  -1 [-3  5  3] 6  7   | [5, 3]          |
| 1  3  -1  -3 [5  3  6] 7   | [6]             |
| 1  3  -1  -3  5 [3  6  7]  | [7]             |
|----------------------------------------------|

Monotonic Stack

Monotonic Queue 和 Monotonic Queue 是类似的，不过只在栈顶进行操作。主要用于 O(n) 解决 NGE 问题（Next Greater Element），也就是，对序列中每个元素，找到下一个比它大的元素。（当然，“下一个” 可以换成 “上一个”，“比它大” 也可以换成 “比他小”，原理不变。）

单调递减栈可保证当某元素 input[i] 在栈中时，input[i + 1..curr] 中定没有大于 input[i] 的元素，那么有

• 每个元素被 pop 时，input[curr] 一定是其向右第一个大于它的元素
• input[curr] 入栈时，栈顶元素一定是其向左第一个大于它的元素（可用反证法证明

单调递增栈可保证当某元素 input[i] 在栈中时，input[i + 1..curr] 中定没有小于 input[i] 的元素，那么有

• 每个元素被 pop 时，input[curr] 一定是其向右第一个小于它的元素

• input[curr] 入栈时，栈顶元素一定是其向左第一个小于它的元素（可用反证法证明