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                     // 初始化接雨水的总量为0hleft, hright := 0, 0        // 初始化左边和右边的最大高度为0left, 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
}

代码解释：

初始化：
- res 初始化为0，用于存储接雨水的总量。
- hleft 和 hright 初始化为0，分别用于记录左边和右边的最大高度。
- left 和 right 分别指向数组的开始和结尾。
遍历数组：
- 在每一步中，更新左边和右边的最大高度。
- 如果 hleft 小于 hright，说明左边可以接雨水，此时计算当前位置能接的雨水量，并加到总量 res 上。
- 否则，说明右边可以接雨水，同样计算当前位置能接的雨水量，并加到总量 res 上。
移动指针：
- 根据 hleft 和 hright 的比较结果，移动左指针或右指针。
返回结果：
- 返回接雨水的总量 res。