zzx0826 @ 2019-11-23 14:24:51
#include<bits/stdc++.h>
using namespace std;
struct node{
int num;
int id;
}a[1000005];
int n,k;
long long ans[100005];
deque<node>q;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].num;
a[i].id=i;
}
q.push_front(a[1]);
for(int i=2;i<=n;i++){
while(q.size()&&q.back().num>=a[i].num)q.pop_back();
q.push_back(a[i]);
if(q.front().id<=i-k)q.pop_front();
if(i>=k) cout<<q.front().num<<" ";
}
q.clear();
cout<<endl;
q.push_front(a[1]);
for(int i=2;i<=n;i++){
while(q.size()&&q.back().num<=a[i].num)q.pop_back();
q.push_back(a[i]);
if(q.front().id<=i-k)q.pop_front();
if(i>=k)cout<<q.front().num<<" ";
}
return 0;
}by manyc @ 2023-04-02 22:11:57
@_zzx0826 似乎少了点东西？反正我没细看ACcode参考下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],n,k;
deque<int> p;
deque<int> q;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
while(p.size()&&i-p.front()+1>k) p.pop_front();
while(p.size()&&a[p.back()]>=a[i]) p.pop_back();
p.push_back(i);
if(i>=k) cout<<a[p.front()]<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++){
while(q.size()&&i-q.front()+1>k) q.pop_front();
while(q.size()&&a[q.back()]<=a[i]) q.pop_back();
q.push_back(i);
if(i>=k) cout<<a[q.front()]<<" ";
}
return 0;
}