题解：P1886 滑动窗口 /【模板】单调队列

#include<bits/stdc++.h>//万能头
using namespace std;
#define N 1000010
int n, a[N], q[N], head, tail, k;

int main() {
    ios::sync_with_stdio(0);//这就不说了
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    // 找最小值
    head = tail = 0;
    for (int i = 1; i <= n; i++) {
        // 移除过期元素
        while (head <= tail && q[head] + k - 1 < i) ++head;
        // 维护队列单调递增
        while (head <= tail && a[q[tail]] >= a[i]) --tail;
        q[++tail] = i;
        // 输出当前窗口的最小值
        if (i >= k) cout << a[q[head]] << ' ';
    }
    cout << '\n';
    
    // 找最大值
    head = tail = 0;
    for (int i = 1; i <= n; i++) {
        // 移除过期元素
        while (head <= tail && q[head] + k - 1 < i) ++head;
        // 维护队列单调递减
        while (head <= tail && a[q[tail]] <= a[i]) --tail;
        q[++tail] = i;
        // 输出当前窗口的最大值
        if (i >= k) cout << a[q[head]] << ' ';
    }
    
    return 0;//好习惯
}