算法笔记:单调队列
2023-12-23 23:18:06
单调队列
定义:队列中元素之间的关系具有单调性,队首和队尾都可以进行出队操作,只有队尾可以进行入队操作
应用:解决滑动窗口类问题
涉及数据结构:双向队列(deque)
实现:
- 左掐头:把队列左边(front边)超出窗口的部分pop
- 右去尾:把队列右边(back边)大于(小于)当前值的部分pop
- 右入队:从右边(back边)入队
- 判断输出左边(front)第一个元素
基本操作:
que.size(); //返回队列中元素个数
que.empty(); //判断是否为空
que.front(); //返回第一个元素的引用
que.back(); //返回最后一个元素的引用
que.push_back() //在序列的尾部添加一个元素。
que.push_front() //在序列的头部添加一个元素。
que.pop_back() //移除容器尾部的元素。
que.pop_front() //移除容器头部的元素
que.clear() //移出所有的元素,容器大小变为 0。
例题:P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
输出第一行为每次窗口滑动的最小值,第二行为每次窗口滑动的最大值
输入 :
8 3
1 3 -1 -3 5 3 6 7
输出:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k;
int a[N],ans[N];
deque<int> que;
int main(){
//输入
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
// ...
for(int i=1;i<=n;i++){
while(!que.empty()&&que.front()<=i-k) que.pop_front();
while(!que.empty()&&a[que.back()]>=a[i]) que.pop_back();
que.push_back(i);
if(i>=k) cout<<a[que.front()]<<" ";
}
cout<<endl;
que.clear();
for(int i=1;i<=n;i++){
while(!que.empty()&&que.front()<=i-k) que.pop_front();
while(!que.empty()&&a[que.back()]<=a[i]) que.pop_back();
que.push_back(i);
if(i>=k) cout<<a[que.front()]<<" ";
}
return 0;
}
文章来源:https://blog.csdn.net/weixin_67421731/article/details/132789050
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!