NOTES · 学习笔记
接雨水:每个位置能接多少,取决于较矮的那一边
题目
题目要求计算一共接了多少水。每个位置能接多少水,取决于它左右两根柱子较矮的那一根:接水量 = min(左边最高, 右边最高) - 当前高度。
我们看示例 2:height = [4,2,0,3,2,5]。一开始 left=0,right=5,height[left]=4,height[right]=5,leftMax=0,rightMax=0,ans=0。
因为 height[left] < height[right],所以我们要处理左边。此时 height[left]=4,leftMax=0:当前的 4 是目前遇到的最高柱子,它本身不能接水,然后 left++。
变成 left=1,height[left]=2,现在才计算:leftMax=4,当前高度=2,接水 = 4-2 = 2,所以 ans=2。接下来继续移动 left——因为右边的 5 比左边当前的柱子高,所以我们可以继续处理左边。left 移动到高度为 0 的位置时,leftMax 仍然是 4,可以接 4-0=4;移动到高度为 3 的位置:4-3=1;移动到高度为 2 的位置:4-2=2。此时左边这些位置一共接了 2+4+1+2=9。最后左右指针相遇,遍历结束,得到答案 9。
实现代码:
func trap(height []int) int {
left := 0 // 左下标
right := len(height)-1 // 右下标
ans := 0 // 输出答案
leftMax := 0 // 左边最大高度
rightMax := 0 // 右边最大高度
for left < right { // 防止一个元素遍历两次
if height[left] < height[right] {
if height[left] >= leftMax {
leftMax = height[left] // 我们找到左边最大元素更新到leftmax中
} else {
ans += leftMax - height[left] // 计算出所有答案
}
left++
} else {
if height[right] >= rightMax {
rightMax = height[right]
} else {
ans += rightMax - height[right]
}
right--
}
}
return ans
}