单调队列

---

前置技能点：

队列

问题：

对于一个长度为 n 的序列a，我们希望知道所有以 k 为长度的子序列的区间最小/大值。

struct Node{ int id; int v;//value }a[NodeNum];//a[i]的大小由成员变量v决定

思路：

可以以O(k)的复杂度暴力枚举得到 minl+k−1i=la[i] ，由于 a 中长度为k的子序列共有 n−k+1 个，故复杂度为 O(n2) 。

可以通过线段树进行处理，从而减小查询任意一个区间的最值的复杂度，建树复杂度为 O(nlogn) ，查询复杂度为 O(logn) 。

还可以将 a 序列压入一个按v排序的堆，每次区间整体右移一格，由 [l,l+k) 变为 [l+1,l+k] 时将 a[l+k] 元素压入堆。然后循环判定堆顶元素，若堆顶元素的下标小于等于 l 则删除，最后堆顶的元素就是minl+ki=l+1a[i]，堆的插入删除复杂度均为 O(logn) 。

概念引入：

设 (minl+k−1i=la[i]).id=x ， (minl+k−1i=l+1a[i]).id=x′ 。 若 x==l ，则 x′>x 否则 x′==x 。

设 (minl+k−1i=l+1a[i]).id=y 若 a[l+k].v<=a[y].v ，则 minl+ki=l+1a[i]).id==l+k 否则 minl+ki=l+1a[i]).id==y 。

那么就可以维护一个单调递增的队列，用于存储当前区间的最小元素，以及当前区间内队列中每一个元素右边的子序列中的最小元素。

当求解 minl+k−1i=la[i] 时 若 queue[head].id==l−1 ，则可以将它弹出队列。 同时将 a[l+k−1].v 与 queue[tail].v 进行大小判定，若 queue[tail].v>=a[l+k−1].v 则将队尾删除，循环判定直到队列为空或 queue[tail].v<a[l+k−1].v ，询问 O(1) ，空间复杂度 O(n)

拓展：

对于弹出队首，删除队尾元素以及压入元素条件的判定 求凸包对于其他性质的运用 单调栈

例题：

poj 2823 给定序列长度n< 106 ，窗口大小 k <script type="math/tex" id="MathJax-Element-2129">k</script>，将窗口放到序列上，从左往右一格一格移动窗体，输出每个状态窗体中数字的最小值和最大值。 解题报告