题解 | #容器盛水问题# go + 动态规划

go + 动态规划

/**
 * max water
 * @param arr int整型一维数组 the array
 * @return long长整型
*/
func maxWater( arr []int ) int64 {
    n:= len(arr)
    if n == 0 {
        return 0
    }

//     1.记录height中的每个元素，从左向右扫描并记录右边的最大高度
//     2.记录height中的每个元素，从右向左扫描并记录右边的最大高度
//     3.将左右位置元素对比取最小的元素，减去数组当前元素的高度

    //记录左边每个元素最大高度
    leftMax := make([]int, n)
    leftMax[0] = arr[0]
    for i:=1; i< n; i++{
        leftMax[i] = max(leftMax[i-1], arr[i])
    }

    //记录右边每个元素最大高度
    rightMax := make([]int, n)
    rightMax[n-1] = arr[n-1]
    for i:=n-2; i>=0; i--{
        rightMax[i] = max(rightMax[i+1], arr[i])
    }

    sum := 0
    for i:=1; i<n-1; i++{
        height := min(leftMax[i], rightMax[i])
        sum += max(0, height-arr[i])
    }

    return int64(sum)
}


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