单调队列
简介
顾名思义，队列内的元素是单调的；承载的数据结构是双端队列。队列中存放的为数组索引，队列头元素为窗口的最大(最小)元素
- 队头删除不符合有效窗口(有些题目限制了窗口的大小)的元素(个人倾向于左边的为队头,右边的为队尾 )
- 队尾删除不符合单调性的元素(不符合最值的候选元素)
如何使用
- 去尾操作。队尾元素出队列，当队列有新元素待入队时，需要从对尾开始,删除邮箱队列单调性的元素,维护队尾的单调性。
- 去尾巴操作之后，将新元素加入队列
- 删头操作。对头元素出队列，判断对头元素是否在待求解的区间内，如果不在，就将其删除。(就是判断区间长度是否满足条件的)
- 取解操作。经过上述的操作，取出队头的元素就是当前区间的极值
注:去尾和删除操作可以互换位置,但是新元素入队列必须是在去尾操作之后.很好理解,为了满足单调性.
时间复杂度为O(n)，nums 中的每一个元素最多被入栈一次及出栈一次，没有任何多余的操作
如果不想手动维护单调队列，可以使用 优先队列 来 充当队列。
队首是我想要的值，只有单调递增，单调递减两种情况，本质上都是 最近n个值的最大值 or 最小值。
模板
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: window = [] res = [] for i in range(0, len(nums)): # 让队列内存放 k-1个元素 # 因为待会 i 会放到 队尾，从队首到队尾要保证有k个数字，所以是和对首的系数比较 while window and i - window[0] >= k: window.pop(0) while window and nums[i] > nums[window[-1]]: window.pop() window.append(i) if i >= k - 1: res.append(nums[window[0]]) return res
速通
单调队列 常用来维护数据流中的最大值or最小值。最大值或者最小值还是放在队列首部的。
862. 和至少为 K 的最短子数组 209的升级版，想清楚为什么是递增队列？只有维持的是递增队列，才能在左出队的时候，可能更新结果
