单调栈

定义：内部元素满足单调性的栈。

用途：线性时间内处理出数组中每一个 \(i\) 左边/右边 第一个 大于/小于 \(a_i\) 的位置。

模板题：P5788 【模板】单调栈

题意：令 \(f(i)\) 为 \(i\) 右边第一个大于 \(a_i\) 的位置。输出 \(f(i)\) , \(i = 1...n\) 。

解法："右边"说明单调栈处理需要倒序，第一个大于说明单调栈需要维护由栈顶到栈底递增。所以我们用一个 pair 类型的 stack 来完成即可，first 用来存 \(a_i\) ， second 用来存 \(i\) 。

时间复杂度：

很显然是 \(O(n)\) 。

Code

经典例题：

\(No.1\)

AcWing131. 直方图中最大的矩形

对于 \(h_i\) 找到其左边第一个小于其高度的楼栋记为 \(l_i\) ，右边第一个小于其高度的楼栋记为 \(r_i\) ，那么答案就为 \(\max\) { \(a_i \cdot (r_i - l_i - 1)\) } 。

Code

\(No.2\)

P6503 [COCI2010-2011#3] DIFERENCIJA

考虑动态规划，\(fmax_i\) 表示以 \(i\) 为结尾的区间的 \(\max\) 之和， \(fmin_i\) 表示以 \(i\) 为结尾的区间的 \(\min\) 之和。

对于维护 \(fmax\) ，我们可以知道 \(a_i\) 最多影响到其前一个比它大的数位置 $ + 1$ 的位置。所以我们用单调栈维护每一个 \(a_i\) 前一个比它大的数的位置，记这个位置为 \(nxt_i\) ，那么转移即为即为 \(fmax_i = fmax_{nxt_i} + a_i \cdot (i - nxt_i)\) 。

对于 \(fmin_i\) 同理，不再赘述。

Code

\(No.3\)

P1950 长方形

其实就是将上面一题从一维抽象成二维。

先预处理一个 \(f_{i,j}\) 表示第 \(i\) 行以 \((i,j)\) 为结尾的连续 "." 的最前面一个 "." 的位置：

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        f[i][j] = j;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        if(ch[i][j - 1] == '.')f[i][j] = f[i][j - 1];

然后用 \(ans_{i,j}\) 表示以 \((i,j)\) 为左下角能构成的矩形数。

我们该怎么推状态转移方程呢。

举两个例子吧：（原题的 \(.\) 用 # 代替）

* * #
* # #
# # #
# # #

这种情况 \(ans_{4 , 3} = ans_{2 , 3} + (4 - 2) \times (3 - f_{4,2} + 1)\)

# # #
# # #
* # #
* * #

这种情况

\(ans_{3 , 3} = 2 \times 3 = 6\)

\(ans_{4 , 3} = 1 \times 4 = 4\)

仔细思考，对于某一 # 点 \((i, j)\) ，考虑找到在它之上离它最近的 \(f\) 值大于它的点，记这个点为 \((x ,j)\) 。

则 \(ans_{i,j} = ans_{x,j} + (i - x) \times (j - f_{i,j} + 1)\) 。

这个式子建议配合以上的例子仔细思考，我认为还是有一定思维难度的。

而对于一个 \(*\) 点，可以把它视为一堵墙，或者理解成边界。遇到它我们只需要把 \(ans_{i,j}\) 赋为 \(0\) ，然后将该列的该点以上的值全部从栈中退出即可。

说起来确实有点抽象，可以结合代码理解。

Code