概念：什么是单调队列

单调队列，顾名思义就是单调的队列，那有些人就说了 “那你这单调队列和 priority_queue 有什么区别” 区别可大了，首先 priority_queue 是一个堆，其次，单调队列维护单调性的方式可不是把里面的东西排序，而是直接弹出元素。

单调队列的好处就是可以在 $O(n)$ 的时间内知道一个数组所有长度为一个固定值的子区间中的极值。

模拟：单调队列如何维护单调性

假设现在我们有一个序列：

$A = \{ 1,3,-1,-3,5,3,6,7 \}$

我们要求他所有长度为 $3$ 的子区间中的最大值，现在我们就假设我们只有一个队列，看看如何得出我们要的答案

/*

初始值：
Q = empty

插入 1 ，队列：
Q = {1}

插入 3 ，由于我们的队首需要是答案，所以把1弹出：
Q = {3}

插入 -1，-1 < 3 符合队列头部是答案的需求，不用动
Q = {3, -1}

插入 -3，由于 3 已经超出了规定子区间长度3的范围，弹出，同时 -1 > -3 所以不用动
Q = {-1, -3}

插入 5 ，由于所有的数都小于 5 ，所以弹出全部
Q = {5}

插入 3
Q = {5, 3}

插入 6 ，6最大，弹出全部
Q = {6}

插入 7， 7最大，弹出全部
Q = {7}

*/

自此我们大概了解了这个单调队列的规则。

实现：对于刚刚思路的代码化

// 基础的函数
bool empty() {
    return st == ed; // 左闭右开
}

void clear() {
    st = ed = 0;
}


// 使用求最大值
clear();
for (int i = 1; i <= n; i++) {
    while (!empty() && a[i] >= a[q[ed - 1]]) {
        ed--;
    }
    q[ed++] = i;
    while (!empty() && i - q[st] >= k) {
        st++;
    }
    if (i >= k) {
        printf("%d ", a[q[st]]);
    }
}