基本算法

简介

单调栈是一种算法，它可以用一次扫描 (O(n)) 时间求出序列中每个数向左和向右的第一个大于它的数，也可以用一次扫描 (O(n)) 时间求出序列中每个数向左和向右的第一个小于它的数。

以大于为例：

用单调栈求左边第一个大于的数：

有数列(ig<aig>)。

对于一个数 (a_i) 前面的两个数 (a_p,a_q, quad p<q<i)，若 (a_p<a_q)，则对于所有 (jge i)， (a_p) 都不可能成为 (a_j) 的答案。

单调栈就是对于每个数维护可能成为其答案的下标集合，然后从里面快速选出答案。

具体地，算法流程是：

一、从左到右扫描数列，开一个空栈 (stk)，栈顶为 (stk[tp])

二、对于每个数 (a_i)，

在栈不为空且 (stk[tp] le a_i) 的时候使栈不断 (pop)
停止 (pop) 后，若栈不为空， (stk[tp]) 就是 (a_i) 左边第一个大于其的数，否则 (a_i) 左边没有大于其的数。
将 (a_i) 加入到栈顶

从以上算法可以看出，每个数 (a_i) 都是会被加入栈里的，那么在以后的扫描过程中，让 (a_i) 从栈中弹出的那个数一定就是 (a_i) 右边第一个大于其的数，若自始至终 (a_i) 没有被弹出，则 (a_i) 右边没有大于其的数。

至此，可以用单调栈一次扫描求出每个数左边和右边第一个大于其的数，对于小于，只需简单地魔改一下算法就可以了，用到的理论也是高度类似的

对于基本算法的正确性的证明

需要证明的仅仅是求左边第一个大于的数的正确性，懂的都懂。

那么对于每个数 (a_i)，在 算法流程 扫描到 (a_i)，执行到 二-2 的时候，为什么能直接确定答案？

首先可以确定栈中没有不可能成为 当前数的答案 的数 (当然也没有不可能成为以后数的答案的数)，此时选栈顶，即最靠近当前数的数，就是答案。

为什么可以确定这个事实? 可以用归纳法证明，在这里就不证了，仅给出参考思路：

假设扫描到 (a_i),

用归纳法证明到步骤 二-1 之前，栈中没有不可能成为 (a_i) 答案的数，所有可能成为 (a_i) 答案的数都在栈中。
用归纳法证明到步骤 二-1 之前，从栈底到栈顶是一个单调递减的数列，这就可以证明执行完步骤 二-1 之后栈顶就是答案

更深一点的应用

可以用归纳法证明，对于数列 (ig<aig>)，在使用基本算法求每个数的左边的第一个大于其的数时，对于当前扫描的数 (a_i)，单调栈实际上是维护的数列 (ig<aig>_{1cdots i}) 的后缀最大值（从栈顶到栈底，就是 (max(a[icdots i])、max(a[i-1cdots i])、cdots、max(a[1cdots i])) 去重后的结果）。

于是在单调栈的过程中，可以见到整个数列所有子串的最大值，至于有多少应用嘛……不知道。

应用

1

求 (sum_{l=1}^nsum_{r=l}^n max(a_{lcdots r}))。

根据上面的 更深一点的应用 单调栈 (O(n)) 搞，很不错。

还可以枚举所有 (a_i)，算出 max 是 (a_i) 的区间有多少个，这个也可以用单调栈求出来。

1的升级版

(f(X,Y) = sum_{l=X}^Ysum_{r=l}^Y max(a_{lcdots r}))

(Q) 次询问不同的 (f(X,Y))

要求 (O((n+Q)log n))。

似乎不太可做，待补。

2

给定数列 (a) ，求 (max{a[Lcdots R]}*(a_R-a_L)) 的最大值。

枚举 (max{a[Lcdots R]})，再讨论一下，就做完了。（用 st表可以做到 (O(nlog n))）

如果把 (a_R-a_L) 换成 (R-L+1)，可以做到 (O(n))。

3

给定数列 (a)，求有几对 ((x,y)) 满足：
(max(a[x+1cdots y-1]) le min(a[x],a[y]))。

顺便可以求出具体方案。

单调栈求左边第一个大于的数的过程中，被一个数弹掉的所有数以及此数的答案，就是所有可以使这个数作为 (y) 的 (x)。

这样的对数是 (O(n)) 的。

顺便如果把题目中式子的小于等于号改成小于号，此算法也能胜任，而且针对小于号还有一种其它的算法：
所有 ((x,y)) 都是某一个数的 ((左边第一个大于的，右边第一个大于的))。

4

给定矩阵，求面积最大的和 (>0) 的子矩阵。

首先枚举上下边界压缩一维（就像求最大子矩阵和一样）。

然后问题就变成了在一个数列中，对于每个数求出最左边的小于其的数。

当然这并不是单调栈，但是比较像单调栈。（其实是维护了前缀最小值）

总复杂度 (O(n^3log n))