我的位置:首页 > .Net系列>C++

单调队列

时间:2020-02-07 16:57:00 来源:互联网 作者: 神秘的大神 字体:

1.单调队列简介:

单调队列是一种数据结构,类似如单调栈,但里面的元素必须在一个区间内,如果“过时”就要出队。所以,单调队列可以在两端进行出队,但只能再队尾入队。按此性质,传统的队列已无法满足需求,需要使用双端队列,再C++的STL里,双端队列定义在deque里:

#include <deque>

定义:

deque <int> d;

deque的成员函数:

 
函数名 功能描述
push_back 在队尾插入
push_front 在对头插入
 pop_back  在队尾删除
 pop_front  在队头删除
 empty  判断是否为空
 front  队头元素
 back  队尾元素

 

进队时需先判断是否有元素破坏单调性,如果有则pop_back,再判断元素是否过时,如果有则pop_front,最后push_back,用代码表示就是

 1 deque <int> d;//单调队列
 2 int a[10];//存放读入的元素
 3 int n;//元素个数
 4 for(int i=0;i<n;i++){
 5 
 6     //假设进队的是a[i]
 7 
 8     while(!d.empty()&&a[d.back()]<a[i]){//这里以单调递增队列为例,单调递减队列可以把小于号改成大于号
 9         d.pop_back();
10     }
11     while(!d.empty()&&d.front<i-4){//假设单调递增队列的区间长度为4
12         d.pop_front();
13     }
14     d.push_back(i);
15 }

与单调栈相同,进队的元素不会再出队,所以复杂度也是O(n)。

 

 

2.单调队列的功能:

单调队列可以查找区间最小(最大)值,与线段树等复杂度为O(n㏒2n)的算法相比,单调队列复杂度为O(n),更加高速。举个例子,在100,5,30中查找每两个数中最大值。使用单调递减队列,首先100、5入队(一个元素无法找两个数中最大值),没有元素破坏单调性,所以100、5的最大值是队头100,然后30入队,5破坏单调性,出队;100“过时了”,出队,所以5、30的最大值就是队头30。