0042 - Trapping Rain Water
题干
破题
如果能知到每个单位区间左边和右边的最大高度，取其最小值，就是该单位的存雨量。12
链接题目
0032 - Longest Valid Parentheses
解①双向扫描：
可以认为下降和上升是需要匹配的两个阶段，如果事先记录下降前的高度，在一个下降-上升周期结束的时候，就可以回溯计算这个“坑道”的存雨量，不过这有一个前提，就是上升达到的最大高度不小于下降前的最大高度，确保我们正确计算了这个坑道的雨量。但这就带来了一个问题，可能一直到结束，后面都找不到匹配的高度，于是可以参照 0032 里面的双向扫描，再次地从后向前扫描到最后一个下降的“峰”位。
def solve(h: List[int]) -> int:
mode = True
k = 0 # peak
ans = 0
for i in range(1, len(h)):
if mode:
if h[i] > h[i-1]:
mode = not mode
else:
if h[i] < h[i-1]:
mode = not mode
if not mode and h[i] >= h[k]:
ans += sum(map(lambda j: h[k]-h[j], range(k+1, i)))
k = i
mode = True
oldk = k
k = len(h) - 1
for i in range(len(h)-2, oldk-1, -1):
if mode:
if h[i] > h[i+1]:
mode = not mode
else:
if h[i] < h[i+1]:
mode = not mode
if not mode and h[i] >= h[k]:
ans += sum(map(lambda j: h[k]-h[j], range(i+1, k)))
k = i
return ans
但是必须吐槽得是本来 mode 采用得是枚举类型：
from enum import Enum
class Mode(Enum):
Down = 0
Up = 1
但是 Python 的 Enum ，或者说一般地对类的封装是如此地消耗内存，只这一个类的定义，就直接让测试结果的内存消耗从排名靠前掉到了排名靠后！于是替换成了布尔类型。
相比于下面介绍的同复杂度但是一遍扫描的算法，双向扫描的算法要稍微慢一点。
解②双指针：
假设我们事先找到序列里的最大高度3 $h_\text{max}$：
那么在它的左边，从头开始扫描，维护一个到当前位置 $i$ 为止的前缀最大值 $h_\text{left} = \max\lbrace {h_0 \dots h_i}\rbrace$，每个位置的积水就是 $h_\text{left}-h_i$ ；
在它的右边，从尾开始扫描，维护一个到当前位置 $j$ 为止的前缀最大值 $h_\text{right} = \max\lbrace{h_{n-1} \dots h_j}\rbrace$，每个位置的积水就是$h_\text{right}-h_j$ 。
实际上我们不需要真的取寻找这个最大高度，我们只需要确定 $h_\text{left}$ 和 $h_\text{right}$ 不是最大值即可，只要从两边同时开始扫描，比较 $h_\text{left}$ 和 $h_\text{right}$ ，其中较小的那一个计算该位置积水，然后继续前进，直到完成整个序列的扫描，也就是两端相遇。
def solve(h: List[int]) -> int:
lf = 0
rh = len(h) - 1
lf_max = h[lf]
rh_max = h[rh]
ans = 0
while lf < rh:
if h[lf] < h[rh]:
ans += lf_max - h[lf]
lf += 1
lf_max = max(lf_max, h[lf])
else:
ans += rh_max - h[rh]
rh -= 1
rh_max = max(rh_max, h[rh])
return ans
测试时的实际性能足够快，取样表上最快的就是这个版本。
解③单调栈：
单调栈，Monotonic Stack，这是第一次遇到可以恰当地套用这个算法思想的题目。
回到双向扫描的思路，只要序列一直保持不增4，就（把索引位置）入栈，直到遇到一个大于栈顶元素（对应高度）的值 $h_i$，然后弹出所有（对应高度）不超过 $h_i$ 的栈元素，于是可以利用这些元素水平地计算积雨。
每一层的高度是（弹出的）相邻栈元素对应的高度差，长度是每个栈元素 $k_0$ 的前一个栈元素 $k_1$ 与当前位置 $i$ 的差减一：$i-k_1-1$ 。
并且注意，如果在弹出不超过 $h_i$ 的元素后，栈中还有元素，那么弹出的最后一个元素到栈顶元素还有一段积雨，高度差则是 $h[i]-h_\text{last}$。
from itertools import pairwise
def solve(h: List[int]) -> int:
stack = [0]
ans = 0
for i in range(1, len(h)):
if h[i] > h[stack[-1]]:
cache = [stack.pop()]
while stack and h[stack[-1]] <= h[i]:
cache.append(stack.pop())
ans += sum(map(lambda k: (h[k[1]]-h[k[0]])*(i-k[1]-1), pairwise(cache)))
if stack:
ans += (h[i]-h[cache[-1]])*(i-stack[-1]-1)
stack.append(i)
return ans
测试时的实际性能不错。
注解
