单调队列

单调队列最经典的应用就是 求滑动窗口中的最大值/最小值。

滑动窗口示意图：对于数组 [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小为 3

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

滑动窗口显然可以用队列来维护：

把新加入的元素加入队尾
从队头弹出最后一个元素
暴力做法就是每次循环判断队列中是否有重复元素，时间复杂度 $O (n^{2})$

依旧是考虑是否存在 逆序对： $a_{i} > a_{j}$ 同时 $i < j$ ，这种情况下当 $a_{j}$ 加入滑动窗口后， $a_{j}$ 左边和它构成逆序对的元素，一定不会成为之后滑动窗口的 最小值，因为它不仅比 $a_{j}$ 大，还先于 $a_{j}$ 被滑动窗口弹出。

例如：当 -3 加入滑动窗口后，-3 之前的 1, 3, -1 都不会成为最小值了。

删除所有这种逆序对后，得到的就是一个 严格单调上升的队列，该队列的最小值就是队列的队头。

算法流程：

对于这样一个单调队列，我们思考其维护过程
对于新元素 a[i]，将其和 队尾元素 a[j] 依次比较
- 如果 a[i] <= a[j]，弹出队尾元素，重复上述操作
- 如果 a[i] > a[j]，直接加入队尾，此时队列保持严格单调上升
由于窗口是滑动的，因此会有自然出队的情况
- 队列中改存 元素对应的下标
- 当新元素 a[i] 准备入队时，先判断此时的队头元素需不需要自然出队：if (i - q[hh] >= k)
- 队头元素自然出队后，再进行比较和新元素入队操作

核心代码：注意防止越界，先判断队列非空再取队头/尾

cpp

//...
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++) {
        // end point: i, start point: i - k + 1
        if (hh <= tt && q[hh] < i - k + 1) {
            hh ++;
        }

        while (hh <= tt && a[q[tt]] >= a[i]) {
            tt --;
        }

        q[++ tt] = i;

        if (i >= k - 1) {
            cout << a[q[hh]] << " ";
        }
    }

注意要先加入 i，即 q[++ tt] = i;，因为新加入的 a[i] 可能就是最小值。

显然，队头队尾都有弹出，这是一个 双端队列。

单调队列 ​

单调队列