单调队列-滑动窗口

为什么是单调队列
ans：对于当前下标为i的数，找i-k+1 ～ i之间最小的数，如果当前a[i]是整个窗口中最小的数，那么
这个窗口中其他的数必定都是不可能成为答案的，所以将当前窗口中所有>=a[i]的数全部删除。当窗口往后移一位时，此窗口中不在下一个窗口中数需要删除，并将a[i+1]执行同样操作流程。这种优化后的滑动窗口法，就需要单调队列来实现。

具体如何实现
1. 对于当前的下标为i的数，维护一个下标队列，这个窗口中所有>=a[i]的数，在队列中全部删除，然后将i下标入队列，这样对于当前窗口，队列的队首就是窗口中最小值的下标
2. 当窗口往后移动一位时，将队列中不在窗口中的下标删除，并执行1操作

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh = 0, tt = -1;  // tt = -1, hh <= tt表示不为空⚠️

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - q[hh] >= k) hh++;
        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 - q[hh] >= k) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;  //求最大值，最大值应该在队首，所以单调递减
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    return 0;
}