题解
2025-08-05 09:54:22
发布于:上海
8阅读
0回复
0点赞
单调队列还是太吃操作了
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll n,k,a[N];
int main(){
deque<int>q;
cin>>n>>k;
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();
if(i-k>-1)cout<<a[q.front()]<<" ";//队列有k大小的时候正式开始输出
}//以上是最小值
while(q.size())q.pop_front();//清空
cout<<endl;//换行
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();
if(i-k>-1)cout<<a[q.front()]<<" ";//队列有k大小的时候正式开始输出
}//以上是最大值
return 0;
}
这里空空如也
有帮助,赞一个