滑动窗口

//滑动窗口 单调队列
#include<cstdio>
#define ll long long
#define N 1000001
using namespace std;
int n,k;
ll a[N],q[N],q2[N]; //q存值
int b[N],b2[N]; //b存编号

void find_min(){
int head=1,tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&a[i]<=q[tail]){ //若新值较小，直接去掉之前的
tail--; //尾巴表示队列现在的长度
}
q[++tail]=a[i]; //递增的直接加进来，为以后可能的最小值
b[tail]=i;
if(b[head]<=i-k) head++; //头向右移 eg第一次移时 i=k+1
//不判断tail是因为它会变化
if(i>=k) printf("%lld ",q[head]);
}
printf("\n");
}

void find_max(){
int head=1,tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&a[i]>=q2[tail]){
tail--;
}
q2[++tail]=a[i];
b2[tail]=i;
if(b2[head]<=i-k) head++; //头向右移
if(i>=k) printf("%lld ",q2[head]);
}
printf("\n");
}

int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
find_min();
find_max();
return 0;
}

滑动窗口

原文：https://www.cnblogs.com/re0acm/p/14588472.html