什么是单调队列不妨用一个问题来说明单调队列的作用和操作：
不断地向buffer里读入元素，也不时地去掉最老的元素，不定期的询问当前buffer里的最小的元素。
最StraightForward的方法：普通队列实现buffer。
进队出队都是O(1)，一次查询需要遍历当前队列的所有元素，故O(n)。
用堆实现buffer。
堆顶始终是最小元素，故查询是O(1)。
而进队出队，都要调整堆，是O(logn)。
RMQ的方法
使用Segment Tree或Sparse Table，线段树没写过(树状数组用过)，是logn级的；稀疏表不懂，只知道是logn级的。对于这类问题这两种方法也搞得定，但是没有本文主人公来得快。
单调队列的舞台
由于单调队列的队头每次一定最小值，故查询为O(1)。
进队出队稍微复杂点：
进队时，将进队的元素为e，从队尾往前扫描，直到找到一个不大于e的元素d，将e放在d之后，舍弃e之后的所有元素；如果没有找到这样一个d，则将e放在队头(此时队列里只有这一个元素)。
出队时，将出队的元素为e，从队头向后扫描，直到找到一个元素f比e后进队，舍弃f之前所有的。(实际操作中，由于是按序逐个出队，所以每次只需要出队只需要比较队头)。
每个元素最多进队一次，出队一次，摊派分析下来仍然是 O(1)。
上面的话可能还是没能讲出单调队列的核心：队列并不实际存在的，实际存在的是具有单调性的子序列。对这个子序列按心中的队列进行操作，譬如在进队时丢弃的元素，虽然它不存在于这个子序列里，但是还是认为他存在于队列里。
poj 2823是一个典型的单调队列题，不过因为题目要求中大量的输入输出的使得时间要求竟然卡scanf和printf的字符串解析(直接实现要5000ms)，害得我极其猥琐的手动输入输出解析(800+ms)，真是不爽。
另外进队的顺序和出队的顺序并不一定相同，因为这个队列本身是隐含存在的，可以在进队时看成一个队列，出队时看成另一个队列，只要出队的元素在队列中就行。可以想象成一个队列只有头和身，另一个队列只有身和尾，而这身是共用的。
在信息学竞赛的一些应用先介绍单调队列
做动态规划时常常会见到形如这样的转移方程：
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排序的话，则g(k)必然是不降的。
这样，就引导我们使用一个单调队列来维护决策表。对于每一个状态f(x)来说，计算过程分为以下几步：
1、 队首元素出队，直到队首元素在给定的范围中。
2、 此时，队首元素就是状态f(x)的最优决策，
3、 计算g(x)，并将其插入到单调队列的尾部，同时维持队列的单调性（不断地出队，直到队列单调为止）。
重复上述步骤直到所有的函数值均被计算出来。不难看出这样的算法均摊时间复杂度是O(1)的。因此求解f(x)的时间复杂度从O(n^2)降到了O(n)。
单调队列指一个队列中的所有的数符合单调性（单调增或单调减），在信息学竞赛的一些题目上应用，会减少时间复杂度例：广告印刷（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)d的算法来解决，这是单调队列就可以派上用场了。
具体做法是 先正着扫一遍，再倒着扫一遍，找到每一个数的右极限与左极限，最后找出最大值。
代码：
program bensen;
var
temp,ans:int64;
n,p,q,i,j:longint;
a:array[0..400000] of longint;
b,r,l:array[0..400000] of longint;
begin
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.
