模板题,理解思路会运用即可
#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N],hh=0,tt=-1;
int n,k,a[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
while(hh<=tt&&i-k+1>q[hh]) 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++){
while(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
cout<<endl;
return 0;
}