• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

单调栈详解

开发技术 开发技术 4小时前 2次浏览

单调栈

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

用途:线性时间内处理出数组中每一个 (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


程序员灯塔
转载请注明原文链接:单调栈详解
喜欢 (0)