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，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/67301.html
標籤：C++
上一篇：c++中比較好用的“黑科技”