154. 滑动窗口【单调队列】
2023-09-11 14:15:52 时间
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],n,k;
int main(void)
{
cin>>n>>k;
deque<int>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
if(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+1>=1) cout<<a[q.front()]<<" ";
}
puts("");
while(q.size()) q.pop_back();
for(int i=1;i<=n;i++)
{
if(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+1>=1) cout<<a[q.front()]<<" ";
}
return 0;
}
相关文章
- laravel之horizon队列管理系统
- POJ 2823 Sliding Window 单调队列
- 单生产者和单消费者共同操作同一个消息队列需要加锁吗
- 【BZOJ1855】[Scoi2010]股票交易 DP+单调队列
- 如何保证消息队列的高可用?
- 【UESTC 482】Charitable Exchange(优先队列+bfs)
- 【容器适配器/栈队列】leetcode刷题路线(持续更新)
- 【SystemVerilog基础】SV数据类型总结(变量类型、数组、队列、结构体、枚举类型、字符串)
- [LeetCode] Implement Queue using Stacks 用栈来实现队列
- RabbitMQ队列和交换机的相关知识点
- 【bzoj2453】维护队列/【bzoj2120】数颜色 分块+二分