單調隊列，即單調的隊列。有時用于優化1D/1D方程。
例題 Tyvj1305
時間: 1000ms / 空間: 131072KiB / Java類名: Main
描述
輸入一個長度為n的整數序列，從中找出一段不超過M的連續子序列，使得整個序列的和最大。
例如
1，-3,5,1，-2,3
當m=4時，S=5+1-2+3=7
當m=2或m=3時，S=5+1=6 - 1
- 2
- 3
- 1
- 2
- 3
輸入格式
- 第一行兩個數n,m
- 第二行有n個數，要求在n個數找到最大子序和
輸出格式
- 一個數，數出他們的最大子序和
測試樣例
輸入
6 4
1 -3 5 1 -2 3 - 1
- 2
- 1
- 2
輸出
7 - 1
- 1
備注
資料範圍：
100%滿足n,m<=300000
分析
這是一個典型的動态規劃題目，不難得出一個1D/1D方程：
f(i) = sum[i]-min{sum[k]|i-M≤k≤i} - 1
- 1
如果不明白這個方程的來曆，戳這裡
由于方程是1D/1D的，是以我們不想隻得出簡單的Θ(n^2)算法。不難發現，此優化的難點是計算
min{sum[i-M]..sum[i-1]}
。在上面的連結中，我們成功的用Θ(nlgn)的算法解決了這個問題。但如果資料範圍進一步擴大，運用st表解決就力不從心了。是以我們需要一種更高效的方法，即可以在Θ(n)的攤還時間内解決問題的單調隊列。
單調隊列（Monotone queue）是一種特殊的優先隊列，提供了兩個操作：插入，查詢最小值（最大值）。它的特殊之處在于它插入的不是值，而是一個指針（key）（wiki原文：imposes the restriction that a key (item) may only be inserted if its priority is greater than that of the last key extracted from the queue）。所謂單調，指當一組資料的指針1..n（優先級為A1..An）插入單調隊列Q時，隊列中的指針是單調遞增的，隊列中指針的優先級也是單調的。因為這裡要維護優先級的最小值，那麼隊列是單調減的，也說隊列是單調減的。
查詢最小值
由于優先級是單調減的，是以最小值一定是隊尾元素。直接取隊尾即可。
插入操作
當一個資料指針i（優先級為Ai）插入單調隊列Q時，方法如下：
- 如果隊列已空或隊頭的優先級比Ai大，删除隊頭元素。
- 否則将i插入隊頭
比如說，一個優先隊列已經有優先級分别為
{5,3,-2}
的三個元素，插入一個新元素，優先級為2，操作如下：
- 因為2 < 5，删除隊頭，
{3,-2}
- 因為2 < 3，删除隊頭，
{-2}
- 因為2 > -2，插入隊頭，
{2，-2}
證明性質可以得到維護
證明指針的單調減 ：由于插入指針i一定比已經在隊列中所有元素大，是以指針是單調減的。
證明優先級的單調減：由于每次将優先級比Ai大的删除，隻要原隊列優先級是單調的，新隊列一定是單調的。用循環不變式易證正确性。
為什麼删除隊頭：直覺的，指針比i小（靠左）而優先級比Ai大的資料沒有希望成為任何一個需要的子序列中的最小值。這一點是我們使用優先隊列的根本原因。
維護區間大小
當一串資料A1..Ak插入時，得到的最小值是A1..Ak的最小值。反觀dp方程：
f(i) = sum[i]-min{sum[k]|i-M≤k≤i} - 1
- 1
在這裡，A = sum。對于f(i)，我們需要的其實是Ai-M .. Ai的最小值，而不是所有已插入資料的最小值（A1..Ai-1）。是以必須維護區間大小，使隊列中的元素嚴格處于Ai-M..Ai-1這一區間，或者說删去哪些A中過于靠前而違反題目條件的值。由于隊列中指針是單調的，也就是靠左的指針大于靠右的，或者說在優先隊列中靠左的值，在A中一定靠後；優先隊列中靠右的值，在A中一定靠前。我們想要删除過于靠前的，隻需要在優先隊列中從右一直删除，直到最右邊（隊尾）的值符合條件。具體地：當隊頭指針p滿足i-m≤p時。
形象地說，就是忍痛割愛删去哪些較好但是不符合題目限制的資料。
解決問題
這裡用std::list表示隊列，直接按照上面的方法查詢最小值，然後根據方程，
f(k) = s[i] - s[queue.back()]
。直接給出代碼：
#include <iostream>
#include <list>
#include <cstdio>
using namespace std;
int n, m;
long long s[];
// 字首和
list<int> queue;
// 連結清單做單調隊列
int main() {
cin >> n >> m;
s[] = ;
for (int i=; i<=n; i++) {
cin >> s[i];
s[i] += s[i-];
}
long long maxx = ;
for (int i=; i<=n; i++) {
while (!queue.empty() and s[queue.front()] > s[i])
queue.pop_front();
// 保持單調性
queue.push_front(i);
// 插入目前資料
while (!queue.empty() and i-m > queue.back())
queue.pop_back();
// 維護區間大小，使i-m >= queue.back()
if (i > )
maxx = max(maxx, s[i] - s[queue.back()]);
else
maxx = max(maxx, s[i]);
// 更新最值
}
cout << maxx << endl;
return ;
} - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
分析時間複雜度
運用聚合分析，由于一個元素最多進隊一次，出隊一次，while循環總共最多運作Θ(2n)=Θ(n)次，是以算法的攤還效率是Θ(n)。通過單調隊列，實作了線上性複雜度内解決形如：
f[x] = max or min{g(k) | b[x] <= k < x} + w[x]
其中b[x]随x單調不降，即b[]<=b[]<=b[]<=...<=b[n]
g[k]表示一個和k或f[k]有關的函數，w[x]表示一個和x有關的函數 - 1
- 2
- 3
- 1
- 2
- 3
的動态規劃問題。
參考資料：百度百科，wiki
感謝這兩位優美的一問一答：
http://zhidao.baidu.com/link?url=uQuBcPkzFeA_xoxxzKwNCXbdlmihh4ema-RUQwlcdhZ7oDzR9awb2Ec4tjudlYzyyOOpYlaQTGYntLVDDwe5-q
![第四章 棧與隊列[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)