每日一题 3.30 滑动窗口

这是单调队列的模板题

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll const maxn=1e6+5;
int a[maxn],q[maxn];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    int h=1, t=0;
    for(int i=1; i<=n; i++){///维护最小值
        while(h<=t&&q[h]+k<=i) ++h;
        while(h<=t&&a[q[t]]>a[i]) --t;///出现小于当前值的数 
        q[++t]=i;///存储最小值数的位置
        if(i>=k) printf("%d ", a[q[h]]);
    }
    printf("\n");
    h=1, t=0;
    for(int i=1; i<=n; i++){///维护最大值
        while(h<=t&&q[h]+k<=i) ++h;
        while(h<=t&&a[q[t]]<a[i]) --t;///出现大于当前值的数
        q[++t]=i;///存储最大值数的位置
        if(i>=k) printf("%d ", a[q[h]]);
    }
    printf("\n");
    return 0;
}