AcWing 154. 滑动窗口(dueue双端队列)
原题链接
简单
作者:
啊哈哈1
,
2022-04-26 11:08:33
,
所有人可见
,
阅读 145
C++ 代码
#include<bits/stdc++.h>//用deque,可以查询stl
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int s[n];
deque<int>mi,mx;
for(int i=0;i<n;i++){
cin>>s[i];
while(!mi.empty()&&s[i]<mi.back())mi.pop_back();
mi.push_back(s[i]);
if(i>=k-1){
if(i>k-1&&mi.front()==s[i-k]){
mi.pop_front();
}
cout<<mi.front()<<" ";
}
}
cout<<endl;
for(int i=0;i<n;i++){
while(!mx.empty()&&s[i]>mx.back())mx.pop_back();
mx.push_back(s[i]);
if(i>=k-1){
if(i>k-1&&mx.front()==s[i-k]){
mx.pop_front();
}
cout<<mx.front()<<" ";
}
}
return 0;
}
blablabla