單調佇列，即單調遞減或單調遞增的佇列。使用頻率不高，但在有些程式中會有非同尋常的作用。
基本介紹
- 中文名：單調佇列
- 外文名：Monotone queue
- 地位：使用頻率不高，但偶爾有重要作用
- 作用：1D/1D動態規劃等
- 屬於：優先佇列的一種
- 代碼長度：較短，容易調試
- 範圍：限制較多
- OI/ACM重要性：各種神奇算法的基礎
- 基本方程：f[x]=max/min{g(k)}+w[x]
- 基於此的算法：基礎上改進的斜率最佳化，單調棧等
單調佇列的操作,舉例,用堆實現快取數組,RMQ的方法,單調佇列的舞台,在信息學競賽的一些套用,動態規劃·單調佇列的理解,例題1：廣告印刷（ad.pas/c/cpp）,poj_2823_單調佇列,
單調佇列的操作
舉例
不妨用一個問題來說明單調佇列的作用和操作：
不斷地向快取數組裡讀入元素，也不時地去掉最老的元素，不定期的詢問當前快取數組裡的最小的元素。
最直接的方法：普通佇列實現快取數組。
進隊出隊都是O(1)，一次查詢需要遍歷當前佇列的所有元素，故O(n)。
用堆實現快取數組
堆頂始終是最小元素，故查詢是O(1)。
而進隊出隊，都要調整堆，是O(log(n))。
RMQ的方法
單調佇列的舞台
由於單調佇列的隊頭每次一定最小值，故查詢為O(1)。
進隊出隊稍微複雜點：
進隊時，將進隊的元素為e，從隊尾往前掃描，直到找到一個不大於e的元素d，將e放在d之後，捨棄e之後的所有元素；如果沒有找到這樣一個d，則將e放在隊頭(此時佇列里只有這一個元素)。
出隊時，將出隊的元素為e，從隊頭向後掃描，直到找到一個元素f比e後進隊，捨棄f之前所有的。(實際操作中，由於是按序逐個出隊，所以每次只需要出隊只需要比較隊頭)。
每個元素最多進隊一次，出隊一次，攤排分析下來仍然是 O(1)。
上面的話可能還是沒能講出單調佇列的核心：佇列並不實際存在的，實際存在的是具有單調性的子序列。對這個子序列按心中的佇列進行操作，譬如在進隊時丟棄的元素，雖然它不存在於這個子序列里，但是還是認為他存在於佇列里。
另外，進隊的順序和出隊的順序並不一定相同，因為這個佇列本身是隱含存在的，可以在進隊時看成一個佇列，出隊時看成另一個佇列，只要出隊的元素在佇列中就行。可以想像成一個佇列只有頭和身，另一個佇列只有身和尾，而這身是共用的。
在OI賽場上，大多數題目為單調佇列力所不能及的，取而代之的是單調佇列基礎上改進的斜率最佳化，單調棧等，因為其限制條件，故潛力不大。但需要掌握，因為有許多算法建立在其基礎上。
例如斜率最佳化即為f[i] = min/max{f[j] + g[i] * g[j]}，和單調佇列尤為相似。
單調棧即為單調佇列的“棧”版。
這兩種複雜度也是O(n)的。
在信息學競賽的一些套用
動態規劃·單調佇列的理解
做動態規劃時常常會見到形如這樣的轉移方程：
f[x] = max or min{g(k) | b[x] <= k < x} + w[x]
(其中b[x]隨x單調不降，即b[1]<=b[2]<=b[3]<=...<=b[n])
(g[k]表示一個和k或f[k]有關的函式，w[x]表示一個和x有關的函式)
這個方程怎樣求解呢？我們注意到這樣一個性質：如果存在兩個數j, k，使得j <= k，而且g(k) <= g(j)，則決策j是毫無用處的。因為根據b[x]單調的特性，如果j可以作為合法決策，那么k一定可以作為合法決策，並且k是一個比j要優的決策。因為k比j要優，（注意：在這個經典模型中，“優”是絕對的，是與當前正在計算的狀態無關的），所以，如果把待決策表中的決策按照k排序的話，則g(k)必然是不降的。在此例中決策表即f[x].
這樣，就引導我們使用一個單調佇列來維護決策表。對於每一個狀態f(x)來說，計算過程分為以下幾步：
1、 隊首元素出隊，直到隊首元素在給定的範圍中。
2、 此時，隊首元素就是狀態f(x)的最優決策，
3、 計算g(x)，並將其插入到單調佇列的尾部，同時維持佇列的單調性（不斷地出隊，直到佇列單調為止）。
單調佇列指一個佇列中的所有的數符合單調性（單調增或單調減），在信息學競賽的一些題目上套用，會減少時間複雜度
例題1：廣告印刷（ad.pas/c/cpp）
【問題描述】
afy決定給TOJ印刷廣告，廣告牌是刷在城市的建築物上的，城市裡有緊靠著的N個建築。afy決定在上面找一塊儘可能大的矩形放置廣告牌。我們假設每個建築物都有一個高度，從左到右給出每個建築物的高度H1,H2…HN，且0<Hi<=1,000,000,000，並且我們假設每個建築物的寬度均為1。要求輸出廣告牌的最大面積。
【輸入檔案】
中的第一行是一個數n (n<= 400,000 ）
第二行是n個數，分別表示每個建築物高度H1,H2…HN，且0<Hi<=1,000,000,000。
【輸出檔案】
輸出檔案 ad.out 中一共有一行，表示廣告牌的最大面積。
【輸入樣例】
6
5 8 4 4 8 4
【輸出樣例】
24
【解釋】各個測試點一秒，
但就這道題來說，n<= 400,000，我們如果用枚舉不會過全部數據，我們應設計出o(n)的算法來解決，這是單調佇列就可以派上用場了。
注意：這個是單調棧的做法，單調佇列需要兩遍均可彈出。
pascal完整程式
vartemp,ans:int64;n,p,q,i,j:longint;a:array[0..400000]of longint;b,r,l:array[0..400000]of longint;beginfillchar(b,sizeof(b),0);readln(n);for i:=1 to n do read(a[i]);p:=1;q:=0;for i:=1 to n+1 do beginwhile (p<=q) and (a[i]<a[b[q]]) do beginr[b[q]]:=i;dec(q);end;inc(q);b[q]:=i;end;fillchar(b,sizeof(b),0);p:=1;q:=0;for i:=n downto 0 do beginwhile (p<=q) and (a[i]<a[b[q]]) do beginl[b[q]]:=i;dec(q);end;inc(q);b[q]:=i;end;for i:=1 to n do begintemp:=(r[i]-l[i]-1)*a[i];if temp>ans then ans:=temp;end;writeln(ans);end.
測試數據
樣例輸入1【ad.in】
20
12 8 8 30 40 32 19 22 12 32 30 45 15 1937 5 5 6 26 35
樣例輸出1 【ad.out】
144
樣例輸入2 【ad.in】
56
3000 2000 180 190 2890 2900 3120 450560 500 300 2100 2300 480 840 880 890 350 550 450 760 960 860 250 260 1050 11301140 2140 2045 2065 3075 3155 3255 3470 3490 3240 920 930 900 930 980 890 740760 770 825 845 855 950 1980 880 680 690 2380 2390
樣例輸出2【ad.out】
21080
poj_2823_單調佇列
【問題描述】
有N個數，每次從左到右選取M個數，第一行選取每個區間中的最小值輸出，第二行選取最大值並輸出。
【解題思路】
這個是典型的固定k區間的單調佇列。套用的本質思想是，如求最小值： 考慮這樣的一個問題，在某個區間當中如果存在某兩個元素A,B，滿足A的下標小於B的下標，A的值大於B的值，那么A這個數就可以刪掉，不再考慮。求最大值反之。
具體的操作是：從加入第k個數開始，每插入做一次佇列單調性更新：
刪隊尾【單調性】，入隊，刪隊首【下標範圍k以內】，輸出隊首【即最值】。
需要注意的是，這裡用純單調佇列會逾時，把刪隊尾的操作改成二分的話就過了。
#include<stdio.h>#include<stdlib.h>#defineN1000001typedefstruct{intvalue;intindex;}QUE;QUEmin_que[N],max_que[N];intn,k,num[N],front,rear;intdelete_rear_inc(intf,intr,intd){intmid;while(f<=r){mid=(f+r)/2;if(min_que[mid].value==d)returnmid;if(min_que[mid].value>d)r=mid-1;elsef=mid+1;}returnf;}intdelete_rear_dec(intf,intr,intd){intmid;while(f<=r){mid=(f+r)/2;if(max_que[mid].value==d)returnmid;if(max_que[mid].value>d)f=mid+1;elser=mid-1;}returnf;}main(){inti;//while(scanf("%d%d",&n,&k)!=EOF){scanf("%d%d",&n,&k);for(i=1;i<=n;i++)scanf("%d",&num[i]);//單調佇列求最小——維持k區間的遞增佇列min_que[1].value=num[1];min_que[1].index=1;front=1;rear=1;//1->kfor(i=2;i<=k;i++){//刪隊尾，入隊rear=delete_rear_inc(front,rear,num[i]);min_que[rear].value=num[i];min_que[rear].index=i;}printf("%d",min_que[1].value);//隊首即為第一個滑動視窗的最小值//k+1->nfor(i=k+1;i<=n;i++){//刪隊尾，入隊,維持區間範圍rear=delete_rear_inc(front,rear,num[i]);min_que[rear].value=num[i];min_que[rear].index=i;//刪隊首，維持區間範圍if(i-min_que[front].index>=k)front++;//隊首為第i-k+1個滑動視窗的最小值printf("%d",min_que[front].value);}printf("\n");//單調佇列求最大——維持k區間的遞減佇列max_que[1].value=num[1];max_que[1].index=1;front=1;rear=1;//1->kfor(i=2;i<=k;i++){//刪隊尾，入隊rear=delete_rear_dec(front,rear,num[i]);max_que[rear].value=num[i];max_que[rear].index=i;}printf("%d",max_que[1].value);//隊首即為第一個滑動視窗的最大值//k+1->nfor(i=k+1;i<=n;i++){//刪隊尾，入隊,維持區間範圍rear=delete_rear_dec(front,rear,num[i]);max_que[rear].value=num[i];max_que[rear].index=i;//刪隊首，維持區間範圍if(i-max_que[front].index>=k)front++;//隊首為第i-k+1個滑動視窗的最大值printf("%d",max_que[front].value);}printf("\n");//}system("pause");return0;}