悬线法

简介

悬线法能解决的问题用单调栈也可以解决

但是悬线法比较简单

我以前学的好像叫极大化(bushi)

可以解决一些最大矩阵的问题

实现

我们定义 $L_i$ 表示有 $a_i$ 这个高度的一根悬线，往左最多能平移到什么位置

初始化显然，$a_i=i$

考虑转移

• 如果当前 $l_i=1$ 则已经扩展到了
• 如果当前 $a_i > a_{l_i-1}$ 则从当前悬线不能平移到 $L_i-1$
• 如果当前 $a_i \le a_{l_i-1}$ 则当前悬线能平移到 $Li-1$ 往左边平移到的最远的地方

通过摊还分析，可以证明，每个 $l_i$ 最多会被其他的 $l_j$ 遍历一次，因此时间复杂度为 $O(n)$