AcWing 154. 滑动窗口
原题链接
简单
作者:
geats兔
,
2024-03-29 22:11:52
,
所有人可见
,
阅读 1
#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
int hh=0,tt=-1;
for(int i=0;i<n;i++){
if(q[hh]<=i-k) hh++;
while(hh<=tt&&a[q[tt]]>a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++){
if(q[hh]<=i-k) hh++;
while(hh<=tt&&a[q[tt]]<a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
return 0;
}