NOTES · 学习笔记

接雨水:每个位置能接多少,取决于较矮的那一边

LeetCode双指针 · 困难约 4 分钟

题目

题目要求计算一共接了多少水。每个位置能接多少水,取决于它左右两根柱子较矮的那一根:接水量 = 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
}