接雨水
Trapping Rain Water
本机进度仅保存在当前浏览器
题目描述
给定 n 个非负整数表示宽度为 1 的柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]，输出 6。
解题思路
- 按列思考：位置 i 能接的水 = min(左侧最高柱, 右侧最高柱) - height[i]，与 0 取 max。
- 预处理前后缀最大值数组即可 O(n) 计算；再用双指针优化空间：哪一侧最大值更小，就先结算那一侧的列。
- 因为较小的一侧已经确定了该列水位的"瓶颈"，另一侧再高也不影响。
- 另有单调栈解法：栈内维护递减柱子，遇到更高柱时逐层弹出按"横向水层"累加，两种思路都值得掌握。
参考实现
查看参考实现Python · 建议先自行作答
def trap(height):
# 双指针：结算较小侧的列，left_max/right_max 为已扫过的最大高度
l, r = 0, len(height) - 1
left_max = right_max = water = 0
while l < r:
left_max = max(left_max, height[l])
right_max = max(right_max, height[r])
if left_max < right_max:
water += left_max - height[l]
l += 1
else:
water += right_max - height[r]
r -= 1
return water