LeetCode-热题100：42. 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出： 6
解释： 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入： height = [4,2,0,3,2,5]
输出： 9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

代码及注释

func trap(height []int) int {
    res := 0                     // 初始化接雨水的总量为0
    hleft, hright := 0, 0        // 初始化左边和右边的最大高度为0
    left, right := 0, len(height) - 1  // 初始化左右两个指针

    // 循环直到左指针超过右指针
    for left < right {
        // 更新左边的最大高度
        hleft = max(hleft, height[left])
        // 更新右边的最大高度
        hright = max(hright, height[right])

        // 如果左边的最大高度小于右边的最大高度
        if hleft < hright {
            // 计算当前位置能接的雨水量，并加到总量上
            res += hleft - height[left]
            // 移动左指针
            left++
        } else {
            // 计算当前位置能接的雨水量，并加到总量上
            res += hright - height[right]
            // 移动右指针
            right--
        }
    }
    return res  // 返回接雨水的总量
}

// 返回两个数中的最大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 返回两个数中的最小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

代码解释：

1. 初始化：

   • res 初始化为0，用于存储接雨水的总量。
   • hleft 和 hright 初始化为0，分别用于记录左边和右边的最大高度。
   • left 和 right 分别指向数组的开始和结尾。

2. 遍历数组：

   • 在每一步中，更新左边和右边的最大高度。
   • 如果 hleft 小于 hright，说明左边可以接雨水，此时计算当前位置能接的雨水量，并加到总量 res 上。
   • 否则，说明右边可以接雨水，同样计算当前位置能接的雨水量，并加到总量 res 上。

3. 移动指针：

   • 根据 hleft 和 hright 的比较结果，移动左指针或右指针。

4. 返回结果：

   • 返回接雨水的总量 res。

通过这种方法，可以高效地计算出接雨水的总量。