单调队列

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㏒₂n)的算法相比，单调队列复杂度为O（n），更加高速。举个例子，在100，5，30中查找每两个数中最大值。使用单调递减队列，首先100、5入队（一个元素无法找两个数中最大值），没有元素破坏单调性，所以100、5的最大值是队头100，然后30入队，5破坏单调性，出队；100“过时了”，出队，所以5、30的最大值就是队头30。

原文链接:https://www.cnblogs.com/eason66-blog/p/Monotonic_queue.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有