单调队列

数据结构

具有单调性的队列，分为两类：

1. 单调递增队列 对首元素是当前队列的最小值，队列元素单调递增
2. 单调递减队列 对首元素是当前队列的最大值，队列元素单调递减

性质

1. 队列里的元素具有单调性
2. 假设维护区间长度为 $L$ 的最大值，刚入队的元素下标为 $x$ ，则对首元素是区间 $[x-L+1,x]$ 的最大值
3. 由于每个元素只会入队和出队各一次，所以时间复杂度为 $O(n)$
4. 由于只需要维护一个长度为 $L$ 的队列，所以空间复杂度为 $O(L)$