考察经典算法题的推导与证明,而不是背代码。
核心公式
i 的存水量 = max(0, min(leftMax[i], rightMax[i]) - height[i]),其中 leftMax/rightMax 是 i 左右两侧的最高柱。leftMax、rightMax,每次移动较矮的一侧。如果 height[l] < height[r],则 leftMax 是左侧确定的上界,min(leftMax,rightMax)=leftMax,可以安全计算 l 处水量并右移 l;否则对称处理 r。代码(双指针,O(n)/O(1))
def trap(height):
l, r = 0, len(height) - 1
left_max = right_max = 0
ans = 0
while l < r:
if height[l] < height[r]:
left_max = max(left_max, height[l])
ans += left_max - height[l]
l += 1
else:
right_max = max(right_max, height[r])
ans += right_max - height[r]
r -= 1
return ans
为什么正确
height[l] < height[r] 时,右侧至少存在一个不低于 height[r] 的柱子,因此 rightMax >= height[r] > height[l];min(leftMax,rightMax) 由 leftMax 决定,l 处的水量可以立即确定,不会被未来更矮的右侧影响。边界
题目与答案就在本页;收藏、批注和错题重练在应用内