单调队列，即单调的队列。有时用于优化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
输入格式
- 第一行两个数n,m
- 第二行有n个数，要求在n个数找到最大子序和
输出格式
- 一个数，数出他们的最大子序和
测试样例
输入
6 4 1 -3 5 1 -2 3
输出
7
备注
数据范围：
100%满足n,m<=300000分析
这是一个典型的动态规划题目，不难得出一个1D/1D方程：
f(i) = sum[i]-min{ sum[k]|i-M≤k≤i} 如果不明白这个方程的来历，
由于方程是1D/1D的，所以我们不想只得出简单的Θ(n^2)算法。不难发现，此优化的难点是计算min{sum[i-M]..sum[i-1]}。在上面的链接中，我们成功的用Θ(nlgn)的算法解决了这个问题。但如果数据范围进一步扩大，运用st表解决就力不从心了。所以我们需要一种更高效的方法，即可以在Θ(n)的摊还时间内解决问题的单调队列。
查询最小值
由于优先级是单调减的，所以最小值一定是队尾元素。直接取队尾即可。
插入操作
当一个数据指针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} 在这里，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#include #include
using namespace std;int n, m;long long s[300005];// 前缀和list queue;// 链表做单调队列int main() { cin >> n >> m; s[0] = 0; for (int i=1; i<=n; i++) { cin >> s[i]; s[i] += s[i-1]; } long long maxx = 0; for (int i=1; 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 > 1) maxx = max(maxx, s[i] - s[queue.back()]); else maxx = max(maxx, s[i]); // 更新最值 } cout << maxx << endl; return 0;}
分析时间复杂度
运用聚合分析，由于一个元素最多进队一次，出队一次，while循环总共最多运行Θ(2n)=Θ(n)次，所以算法的摊还效率是Θ(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有关的函数 的动态规划问题。
参考资料：百度百科，wiki
感谢这两位优美的一问一答：