每日一题 3月30日 滑动窗口 单调队列

单调队列的模板题。

#include <bits/stdc++.h>
using namespace std;

int a[1000010];
int q[1000010];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    int l=1, r=0;
    for(int i=1; i<=n; i++){
        while(l<=r&&q[l]+k<=i) ++l;
        while(l<=r&&a[q[r]]>a[i]) --r;
        q[++r]=i;
        if(i>=k) printf("%d ", a[q[l]]);
    }
    printf("\n");
    l=1, r=0;
    for(int i=1; i<=n; i++){
        while(l<=r&&q[l]+k<=i) ++l;
        while(l<=r&&a[q[r]]<a[i]) --r;
        q[++r]=i;
        if(i>=k) printf("%d ", a[q[l]]);
    }
    printf("\n");

    return 0;
}