複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/單調隊列/4319570
複製
複製成功

單調隊列

鎖定
單調隊列，即單調遞減或單調遞增的隊列。使用頻率不高，但在有些程序中會有非同尋常的作用。
中文名
單調隊列
外文名
Monotone queue
地    位
使用頻率不高，但偶爾有重要作用
作    用
1D/1D動態規劃等
代碼長度
較短，容易調試
範    圍
限制較多
OI/ACM重要性
各種神奇算法的基礎
基本方程
f[x]=max/min{g(k)}+w[x]
基於此的算法
基礎上改進的斜率優化，單調棧等

目錄

  1. 1 單調隊列的操作
  2. ▪ 舉例
  3. ▪ 用堆實現緩存數組
  4. ▪ RMQ的方法
  1. ▪ 單調隊列的舞台
  2. 2 在信息學競賽的一些應用
  3. ▪ 動態規劃·單調隊列的理解
  1. ▪ 例題1：廣告印刷
  2. ▪ poj 2823 單調隊列

單調隊列單調隊列的操作

單調隊列舉例

不妨用一個問題來説明單調隊列的作用和操作：
不斷地向緩存數組裏讀入元素，也不時地去掉最老的元素，不定期的詢問當前緩存數組裏的最小的元素。
最直接的方法：普通隊列實現緩存數組。
進隊出隊都是O(1)，一次查詢需要遍歷當前隊列的所有元素，故O(n)。

單調隊列用堆實現緩存數組

堆頂始終是最小元素，故查詢是O(1)。
而進隊出隊，都要調整堆，是O(log(n))。

單調隊列RMQ的方法

RMQ即Range Maximum(Minimum) Query，用來求某個區間內的最大值或最小值。使用線段樹或稀疏表是O(log(n))級的。對於這類問題這兩種方法也搞得定，但是沒有單調隊列快。

單調隊列單調隊列的舞台

由於單調隊列的隊頭每次一定最小值，故查詢為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)，並將其插入到單調隊列的尾部，同時維持隊列的單調性（不斷地出隊，直到隊列單調為止）。
重複上述步驟直到所有的函數值均被計算出來。不難看出這樣的算法均攤時間複雜度是O(1)的。因此求解f(x)的時間複雜度從O(n^2)降到了O(n)。
單調隊列指一個隊列中的所有的數符合單調性（單調增或單調減），在信息學競賽的一些題目上應用，會減少時間複雜度

單調隊列例題1：廣告印刷

【問題描述】
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;
begin
fillchar(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 begin
while (p<=q) and (a[i]<a[b[q]]) do begin
r[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 begin
while (p<=q) and (a[i]<a[b[q]]) do begin
l[b[q]]:=i;
dec(q);
end;
inc(q);
b[q]:=i;
end;
for i:=1 to n do begin
temp:=(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>
#defineN1000001
typedefstruct{
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;
else
f=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;
else
r=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->k
for(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->n
for(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->k
for(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->n
for(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;}