单调队列是个什么东西呢，其实没什么滑头，简单望文生义就可以了，单调的队列是也。譬如最小队列 {3, 4, 5, 7}，队列内为非降序，队列头肯定是当前最小的（注意队尾不一定是最大值）。

单调队列的操作(用堆实现buffer。 RMQ的方法 单调队列的舞台)

在信息学竞赛的一些应用

例题：广告印刷（ad.pas/c/cpp）(代码：)

单调队列的操作

不妨用一个问题来说明单调队列的作用和操作：

不断地向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)的算法来解决，这是单调队列就可以派上用场了。

具体做法是 先正着扫一遍，再倒着扫一遍，找到每一个数的右极限与左极限，最后找出最大值。

代码：

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

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.