题解 | #接雨水问题#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * max water
 * @param arr int整型一维数组 the array
 * @return long长整型
*/
func maxWater( arr []int ) int64 {
    // write code here
    // 将每一个柱体看做一个桶，它的最大容量取决于左右侧最大木板高度中较小哪个
    // 因此前后缀数组分别求出它的左右侧木板高度
    n, ans := len(arr), int64(0)
    prevArr, suffixArr := make([]int, n), make([]int, n)
    prevArr[0], suffixArr[n-1] = arr[0], arr[n-1]
    for i := 1; i < n; i++ {
        prevArr[i] = max(prevArr[i-1], arr[i])
    }
    for i := n-2; i >= 0; i-- {
        suffixArr[i] = max(suffixArr[i+1], arr[i])
    }
    for i := 0; i < n; i++ {
        ans += int64(min(prevArr[i], suffixArr[i])-arr[i])
    }
    return ans
}

func max(a, b int) int { if a < b { return b }; return a }
func min(a, b int) int { if a < b { return a }; return b }