$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
单调队列是队列的一种，作用是能在问题中抽象出模型，找出单调性，求极值优化。
也就是在队列中及时取出无效的状态，尽早删除（也就是无法更新答案，一定没有贡献）。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, k, a[N], q[N];
int main() {
    scanf("%d%d", &n, &k);
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        //判断队头是否已经滑出窗口
        if (hh <= tt && i - k + 1 > q[hh]) hh++; //q[hh]滑出窗口，最多只有一个数滑出窗口，所以用if即可
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        //判断队头是否已经滑出窗口
        if (hh <= tt && i - k + 1 > q[hh]) hh++; //q[hh]滑出窗口，最多只有一个数滑出窗口，所以用if即可
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    return 0;
}