單調隊列，即單調的隊列。使用頻率不高，但在有些程序中會有非同尋常的作用。
動態規劃·單調隊列的理解
以下來自某博客+自己補充：
我們從最簡單的問題開始：
給定一個長度為N的整數數列a(i),i=0,1,...,N-1和窗長度k.
要求：
????? f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1
問題的另一種描述就是用一個長度為k的窗在整數數列上移動，求窗里面所包含的數的最大值。
解法一：
很直觀的一種解法，那就是從數列的開頭，將窗放上去，然后找到這最開始的k個數的最大值，然后窗最后移一個單元，繼續找到k個數中的最大值。
這種方法每求一個f(i),都要進行k-1次的比較，復雜度為O(N*k)。
那么有沒有更快一點的算法呢？
解法二：
我們知道，上一種算法有一個地方是重復比較了，就是在找當前的f(i)的時候，i的前面k-1個數其它在算f(i-1)的時候我們就比較過了。那么我們能不能保存上一次的結果呢？當然主要是i的前k-1個數中的最大值了。答案是可以，這就要用到單調遞減隊列。
單調遞減隊列是這么一個隊列，它的頭元素一直是隊列當中的最大值，而且隊列中的值是按照遞減的順序排列的。我們可以從隊列的末尾插入一個元素，可以從隊列的兩端刪除元素。
1.首先看插入元素：為了保證隊列的遞減性，我們在插入元素v的時候，要將隊尾的元素和v比較，如果隊尾的元素不大于v,則刪除隊尾的元素，然后繼續將新的隊尾的元素與v比較，直到隊尾的元素大于v,這個時候我們才將v插入到隊尾。
2.隊尾的刪除剛剛已經說了，那么隊首的元素什么時候刪除呢？由于我們只需要保存i的前k-1個元素中的最大值，所以當隊首的元素的索引或下標小于i-k+1的時候，就說明隊首的元素對于求f(i)已經沒有意義了，因為它已經不在窗里面了。所以當index[隊首元素]<i-k+1時，將隊首元素刪除。
（補充：隊列中的元素主要包括了兩個性質：大小--決定它是否影響f[i]的求值，時效性（刪除隊頭使用）--數組下標決定它是否已經離開了滑動窗口，不在影響f[i]了,刪除隊尾時，是新入隊的時效性>已在隊中的元素了，如果隊尾的取值不如新入隊的元素的值優的話，那么就可以刪除隊尾了。）
從上面的介紹當中，我們知道，單調隊列與隊列唯一的不同就在于它不僅要保存元素的值，而且要保存元素的索引（當然在實際應用中我們可以只需要保存索引，而通過索引間接找到當前索引的值）。
為了讓讀者更明白一點，我舉個簡單的例子。
假設數列為：8，7，12，5，16，9，17，2，4，6.N=10,k=3.
那么我們構造一個長度為3的單調遞減隊列：
首先，那8和它的索引0放入隊列中，我們用（8，0）表示，每一步插入元素時隊列中的元素如下：
0：插入8，隊列為：（8，0）
1：插入7，隊列為：（8，0），（7，1）
2：插入12，隊列為：（12，2）
3：插入5，隊列為：（12，2），（5，3）
4：插入16，隊列為：（16，4）
5：插入9，隊列為：（16，4），（9，5）
。。。。依此類推
那么f(i)就是第i步時隊列當中的首元素：8，8，12，12，16，16，。。。
例題：POJ 2823 滑動窗口
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Sliding Window
| Time Limit:?12000MS | ? | Memory Limit:?65536K |
| Total Submissions:?54158 | ? | Accepted:?15543 |
| Case Time Limit:?5000MS | ||
Description
The array is?[1?3?-1?-3?5?3?6?7], and?k?is 3.
| Window position | Minimum value | Maximum value |
|---|---|---|
| [1??3??-1]?-3??5??3??6??7? | -1 | 3 |
| ?1?[3??-1??-3]?5??3??6??7? | -3 | 3 |
| ?1??3?[-1??-3??5]?3??6??7? | -3 | 5 |
| ?1??3??-1?[-3??5??3]?6??7? | -3 | 5 |
| ?1??3??-1??-3?[5??3??6]?7? | 3 | 6 |
| ?1??3??-1??-3??5?[3??6??7] | 3 | 7 |
Your task is to determine the maximum and minimum values in the sliding window at each position.?
Input
Output
Sample Input
8 3 1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3 3 3 5 5 6 7
1 #define N 1000005 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 #include<cstdio> 6 struct Pai{ 7 int val,pos; 8 }; 9 Pai minque[N],maxque[N]; 10 int minans[N],maxans[N],minhead,maxhead,mintail,maxtail,cur=0; 11 int n,k; 12 int main() 13 { 14 scanf("%d%d",&n,&k); 15 int num; 16 minque[0].val=(1<<31)-1; 17 maxque[0].val=(1<<31)-1; 18 maxque[0].val*=-1; 19 /*使用最大值最小值，為了讓que[0]會被后來的元素占用，防止因為que[0]=0的這個數，代替了本來的最大值或者最小值，所以一開始時會有mintail<0,但是之后馬上就++mintail了，沒有訪問數組，所以不會有越界情況的。*/ 20 for(int i=1;i<=k;++i) 21 { 22 scanf("%d",&num); 23 while(minhead<=mintail&&minque[mintail].val>=num) mintail--; 24 minque[++mintail].val=num; 25 minque[mintail].pos=i; 26 while(maxhead<=maxtail&&maxque[maxtail].val<=num) maxtail--; 27 maxque[++maxtail].val=num; 28 maxque[maxtail].pos=i; 29 } 30 for(int i=k+1;i<=n;++i) 31 { 32 minans[++cur]=minque[minhead].val; 33 maxans[cur]=maxque[maxhead].val; 34 scanf("%d",&num); 35 36 while(minhead<=mintail&&i-minque[minhead].pos>=k)++minhead; 37 while(minhead<=mintail&&minque[mintail].val>=num) mintail--; 38 minque[++mintail].val=num; 39 minque[mintail].pos=i; 40 41 while(maxhead<=maxtail&&i-maxque[maxhead].pos>=k)++maxhead; 42 while(maxhead<=maxtail&&maxque[maxtail].val<=num) maxtail--; 43 maxque[++maxtail].val=num; 44 maxque[maxtail].pos=i; 45 } 46 minans[++cur]=minque[minhead].val; 47 maxans[cur]=maxque[maxhead].val; 48 for(int i=1;i<=cur;++i) 49 printf("%d ",minans[i]); 50 printf("\n"); 51 for(int i=1;i<=cur;++i) 52 printf("%d ",maxans[i]); 53 return 0; 54 }
?
: Cannot modify @@session.sql_log_bin inside a transaction)
)
