其实就是简记一下单调栈的一个很好的理解方式,来源 writings.sh。
以单调递减的单调栈为例。因为如果要加入元素肯定都要先依次弹出栈顶,使加入新元素后能满足单调性。这里就是弹出不比新元素大的栈顶。假设目前准备加入一个新元素 \(x\),正在弹栈(栈顶是需要被弹出的,\(s_{top}\)),栈底是 \(s_0\)。那么,有如下的性质:
- \(s_{top} \leq x\)。按弹出的定义就有了。
- \(s_0\) 一定是目前扫到的最大值。因为如果有不比它小的一定会使它被弹出。
- \(s_{top}\) 在原数组中下一个不比它小的元素为 \(x\)。因为如果中间存在一个不比它小的元素,一定会在 \(x\) 之前使它被弹出。这个可以解决 NGE(Next Greater Element)问题。
- 假设 \(x\) 已经弹出了一些栈中元素,那么由 1 有 \(s_{top} \leq x\),又因为栈是单减的,有 \(lst < s_{top}\)。这就是 “\(x\) 的局部长板效应”:\(lst < s_{top} \leq x\)。
- \(s_{top}\) 是在栈内上一个元素 \(s_{top - 1}\) 和 \(x\) 之间(不含端点)的最大元素。首先由 3 可以得到一部分,而如果在 \(s_{top - 1}\) 到 \(s_{top}\) 之间存在比 \(s_{top}\) 更大的元素 \(nul\),假设 \(nul\) \(\geq s_{top - 1}\),\(s_{top - 1}\) 就会被弹出,矛盾;而如果 \(s_{top - 1} > nul > s_{top}\),它就会存在于 \(s_{top - 1}\) 和 \(s_{top}\) 之间,矛盾。这就是 “\(s_{top}\) 的局部长板效应”。和悬线法有点关系,也可能用于更新贡献(\(s_{top - 1} + 1\) 到 \(s_{top}\) 的位置,见 Pudding Monsters)。