121121a @ 2024-03-22 21:28:04
#include<iostream>
#include<stack>
using namespace std;
int n,m;
int qmin[1000005],qmax[1000005],a[1000005];
int min_deque(){
int h=1,t=1;
for(int i=1;i<=n;i++){
while(h <=t && qmin[h]+m <= i){
h++;
}
while(h <=t && a[i] <= a[qmin[h]]){
t--;
}
qmin[++t]=i;
if(i >= m){
cout<<a[qmin[h]]<<' ';
}
}
cout<<endl;
return 0;
}
int max_deque(){
int h=1,t=0;
for(int i=1;i<=n;i++){
while(h <=t && qmax[h]+m <= i){
h++;
}
while(h <=t && a[i] >= a[qmax[h]]){
t--;
}
qmax[++t]=i;
if(i >= m){
cout<<a[qmax[h]]<<' ';
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
min_deque();
max_deque();
}
by ztksc07 @ 2024-03-22 22:27:38
样例就错了啊喂()
by ztksc07 @ 2024-03-22 22:35:59
while(h <=t && a[i] <= a[qmin[h]]){
t--;
}
改为
while(h <=t && a[i] <= a[qmin[t]]){
t--;
}
下面同理
by 121121a @ 2024-03-23 13:49:29
@ZtkLeo 谢谢