算法笔记:单调队列

2023-12-23 23:18:06

单调队列

定义:队列中元素之间的关系具有单调性,队首和队尾都可以进行出队操作,只有队尾可以进行入队操作

应用:解决滑动窗口类问题

涉及数据结构:双向队列(deque)

实现:

  1. 左掐头:把队列左边(front边)超出窗口的部分pop
  2. 右去尾:把队列右边(back边)大于(小于)当前值的部分pop
  3. 右入队:从右边(back边)入队
  4. 判断输出左边(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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。