Elairin176 @ 2022-10-05 18:22:07
单调队列做法
#include <deque>
#include <iostream>
using namespace std;
#define int long long
struct windows{
int number;
int label;
};
int n,k,maxarr[60000010],iii=0;
windows arr[60000010];
signed main(void){
cin>>n>>k;
deque<windows>mindeque;
deque<windows>maxdeque;
for(int i=0;i<n;i++){
cin>>arr[i].number;
arr[i].label=i;
}
for(int i=0;i<n;i++){
if(i==0){
mindeque.push_back(arr[i]);
maxdeque.push_back(arr[i]);
}else{
while(!mindeque.empty()&&mindeque.back().number<=arr[i].number){
mindeque.pop_back();
}
mindeque.push_back(arr[i]);
while(i>=mindeque.front().label+k) mindeque.pop_front();
if(i>=k-1) maxarr[iii++]=mindeque.front().number;
while(!maxdeque.empty()&&maxdeque.back().number>=arr[i].number){
maxdeque.pop_back();
}
maxdeque.push_back(arr[i]);
while(i>=maxdeque.front().label+k) maxdeque.pop_front();
if(i>=k-1) cout<<maxdeque.front().number<<" ";
}
}
cout<<endl;
for(int i=0;i<iii;i++) cout<<maxarr[i]<<" ";
}
by bamboo12345 @ 2022-10-05 18:56:43
@destructor k=1呢?
by Elairin176 @ 2022-10-05 18:58:59
@bamboo123 嗯,我调调
by Elairin176 @ 2022-10-05 19:04:35
@bamboo123 好了,A了,谢谢指点