欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单调队列(利用C++容器deque实现)原理解析

程序员文章站 2022-07-07 15:46:27
...

1:关于deque

*deque是C++中的一个容器,其底层原理是双端队列(学过数据结构的应该知道,就是对比于普通的队列而言,可以在双端队列的两端进行插入和删除操作,所以用它来操作数据比较方便,但是注意:其底层存储结构并不是连续的存储单元,所以不能用指针加偏移地址去操作)。
* 其头文件为#include< queue >

2:关于单调队列

单调队列其实是一种思想,也就是维护一个单调递增或者单调递减的队列,如果新插入的值比队尾大,就可以直接插入队列,如果比队尾小,就将队尾弹出,知道队尾元素小于这个插入值。所以即可维护一个单调队列。单调队列可以用来计算某个区间内部的最大值或者最小值。

3:利用deque实现单调队列
根据deque的特点,我们可以很清楚的模拟出实现单调队列的过程。

4:例题

单调队列(利用C++容器deque实现)原理解析

单调队列(利用C++容器deque实现)原理解析

//@author:hairu,wu
//@from:ahut
#include<iostream>
#include<queue>
using namespace std;

int n,m;

struct E{
	int num;
	int id;
};

deque<E> q;

int main(){
	cin >> n>> m;
	E e;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		e.num=x;e.id=i;
		if(i==1){//第一个特别输出 
			q.push_back(e);
			printf("0\n");
			continue;
		}
		//对于本题,需要弹出队头在前m个数字之外的数弹出
		while(!q.empty()&&q.front().id<=i-m-1){
			q.pop_front();
		} 
		//输出在前m个中最小的数字
		printf("%d\n",q.front().num);
		//维护单调队列,如果x大于等于队尾元素,直接插入,如果小于队尾元素,则需要弹出对微元素 
		while(!q.empty()&&q.back().num>=x){
			q.pop_back();
		} 
		q.push_back(e); 
	}
	return 0;
} 
相关标签: 难题