题目链接：https://leetcode.cn/problems/trapping-rain-water/
相同题<面试题 17.21. 直方图的水量>链接：https://leetcode.cn/problems/volume-of-histogram-lcci/
思路
方法1：暴力
直观想法：
遍历数组，对于数组中的每个元素，我们找出下雨后水能达到的最高位置Min(Left, Right)，等于两边最大高度的较小值减去当前高度的值。
算法：
- 初始化 ans=0
- 从左往右扫描数组
。初始化 max_Left = 0和 max_Right = 0
。从当前元素向左扫描，找到最高点
- max_Left = max(max_Left, height[j])
。从当前元素向右扫描，找到最高点
- max_Right = max(max_Right , height[j])
。将 max(0, min(max_Left, max_Right) - height[i]) 累加到ans
代码示例
func trap(height []int) int { ans := 0 min := func(a, b int) int{ if a > b{ return b } return a } max := func(a, b int) int{ if a > b{ return a } return b } for i := 1; i < len(height) - 1; i++{ max_Left, max_Right := 0, 0 for j := 0; j < i; j++{ max_Left = max(max_Left, height[j]) } for j := i + 1; j < len(height); j++{ max_Right = max(max_Right, height[j]) } ans += max(0, min(max_Left, max_Right) - height[i]) } return ans }
复杂度分析
- 时间复杂度：O(n2) 每个元素都要从左往右扫描一遍数组
- 空间复杂度：O(1)
方法2：动态编程
直观想法：
既然我们每个元素都要从左往右扫描一遍数组找两边的最大值，不如我们提前把左右两边的最大值存入数组，用空间换时间的方法。
算法
- 找到数组从下标 i 到最左端最高的条形块高度max_Left
- 找到数组从下标 i 到最右端最高的条形块高度max_Right
- 遍历一次数组
。将 max(0, min(max_Left[i], max_Right[i]) - height[i]) 累加到ans
代码示例
func trap(height []int) int { lm := make([]int, len(height)) rm := make([]int, len(height)) min := func(a, b int) int{ if a > b{ return b } return a } max := func(a, b int) int{ if a < b{ return b } return a } for i := range height{ if i == 0{ lm[i] = height[i] }else{ lm[i] = max(height[i], lm[i - 1]) } } for i := len(height) - 1; i >= 0; i--{ if i == len(height) - 1{ rm[i] = height[i] }else{ rm[i] = max(height[i], rm[i + 1]) } } ans := 0 for i := range height{ ans += max(0, min(lm[i], rm[i]) - height[i]) } return ans }
复杂度分析
- 时间复杂度：O(n)
。存储最大高度数组，需要两次遍历，每次 O(n)
。最后更新ans遍历数组，也是O(n)
- 空间复杂度：O(n)
。和方法 1 相比使用了额外的 O(n)空间用来放置 max_Left 和 max_Right 数组。
参考链接：https://leetcode.cn/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
