题解-单调队列
2025-08-05 09:55:10
发布于:上海
8阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005];
int main(){
cin>>n>>k;
deque<int>q;//双端队列
//q.back()尾 q.fronr() 首
//一般从尾进,从头->老死,从尾->淘汰
//pop_back()淘汰 pop_front()老死 push_back 进
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
//淘汰
while(q.size()&&a[q.back()]>a[i]){
q.pop_back();
}
//进
q.push_back(i);
//老死
if(q.front()==i-k)q.pop_front();
//队列有k大小正式开始输出
if(i-k>-1)cout<<a[q.front()]<<" ";
}
cout<<endl;
while(q.size())q.pop_front();//清空队列
//同样的逻辑再来一次
for(int i=1;i<=n;i++){
//淘汰
while(q.size()&&a[q.back()]<a[i]){
q.pop_back();
}
//进
q.push_back(i);
//老死
if(q.front()==i-k)q.pop_front();
//队列有k大小正式开始输出
if(i-k>-1)cout<<a[q.front()]<<" ";
}
return 0;
}
这里空空如也
有帮助,赞一个