单调队列

0
11

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。

<

发布回复

请输入评论!
请输入你的名字