滑窗 单调队列

感谢青竹大佬。

单调队列：固定长度区间的最大值最小值

最大值：维护递减的区间

10 5 6 4 9 6 3 5 8 6 1 2 4

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 7, mod = 1e9 + 7;
typedef long long ll;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, k, a[maxn];
int head, tail, que[maxn];
int maxx[maxn], minx[maxn];
int main() {
    n = read();
    k = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && a[que[tail]] > a[i]) tail--;
        que[++tail] = i;
        while (head <= tail && que[head] <= i - k) head++;
        if (i >= k) minx[i] = a[que[head]];
    }
    head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && a[que[tail]] < a[i]) tail--;
        que[++tail] = i;
        while (head <= tail && que[head] <= i - k) head++;
        if (i >= k) maxx[i] = a[que[head]];
    }
    for (int i = k; i <= n; i++) printf("%d ", minx[i]);
    printf("\n");
    for (int i = k; i <= n; i++) printf("%d ", maxx[i]);
    printf("\n");
    return 0;
}

#include <cstdio>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
const int N = 1e6 + 7;
typedef long long ll;
int n, k, a[N];
int L, R, que[N];
int maxx[N], minx[N];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    L = 1, R = 0;  // 先维护一个递增的队列，用来找区间最小值
    rep(i, 1, n) {
        while (L <= R && a[que[R]] > a[i]) R--;
        // 如果单调队列里有值 而且 队列尾部的值大于当前值 弹出
        que[++R] = i;
        while (L <= R && que[L] <= i - k) L++;
        // 弹出 队列头部 超出了k范围的下标
        if (i >= k) minx[i] = a[que[L]];
    }
    L = 1, R = 0;  // 反过来
    rep(i, 1, n) {
        while (L <= R && a[que[R]] < a[i]) R--;
        que[++R] = i;
        while (L <= R && que[L] <= i - k) L++;
        if (i >= k) maxx[i] = a[que[L]];
    }
    rep(i, k, n) printf("%d ", minx[i]);
    putchar(10);
    rep(i, k, n) printf("%d ", maxx[i]);
    putchar(10);
    return 0;
}