AcWing 154. 滑动窗口
原题链接
简单
作者:
continue_8
,
2024-04-09 22:24:37
,
所有人可见
,
阅读 1
#include<iostream>
#include<deque>
//双端队列 常用函数有push_back push_front
//pop_back pop_front front()和back()——访问deque头尾元素
using namespace std;
const int N=1e6+10;
int a[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
deque<int> q;
//找最小值
for(int i=1;i<=n;i++){
while(q.size()&&q.back()>a[i])
q.pop_back(); //把大于a[i]的队内元素都出队
q.push_back(a[i]);
if(i-k>0&&q.front()==a[i-k]) //判断队头是否滑出了窗口 若是则将队头出队
q.pop_front();
if(i>=k) //窗口已形成
cout<<q.front()<<" ";
}
q.clear(); //清空
cout<<endl;
//找最大值
for(int i=1;i<=n;i++){
while(q.size()&&q.back()<a[i])
q.pop_back(); //把小于a[i]的队内元素都出队
q.push_back(a[i]);
if(i-k>0&&q.front()==a[i-k]) //判断队头是否滑出了窗口 若是则将队头出队
q.pop_front();
if(i>=k) //窗口已形成
cout<<q.front()<<" ";
}
return 0;
}