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
0 <= n <= 3 * 104
0 <= height[i] <= 105

思路#

看图¹（看不清请切换为亮色背景）：

由图，我们只需记录每根柱子左侧、右侧最高的柱子高度即可，欲求某一柱子位置上能有多少水，只需使用左右最高值中较小者（木桶理论，决定存多少水的是短板），减去当前高度即可。

代码#

func trap(height []int) int {
    n := len(height)
    // left 数组用于记录某一柱子左侧的最高值
    var left = make([]int, n)
    // right 数组用于记录其右侧最高值
    var right = make([]int, n)

    // 通过两个遍历获取 left, right
    for i := 1; i < n; i++ {
        left[i] = max(left[i-1], height[i-1])
    }

    for i := n - 2; i >= 0; i-- {
        right[i] = max(right[i+1], height[i+1])
    }

    // 计算有多少水
    water := 0
    for i := 0; i < n; i++ {
        level := min(left[i], right[i])
        water += max(0, level-height[i])
    }

    return water
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/↩