1.單調隊列簡介： 單調隊列是一種數據結構，類似如單調棧，但裡面的元素必須在一個區間內，如果“過時”就要出隊。所以，單調隊列可以在兩端進行出隊，但只能再隊尾入隊。按此性質，傳統的隊列已無法滿足需求，需要使用雙端隊列，再C++的STL里，雙端隊列定義在deque里： #include <deque> ...
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。
