042.接雨水 Trapping Rain Water

Description Hard

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 trap

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

Example
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
Solution
func trap(height []int) int {
    if len(height) < 3 {
        return 0
    }
    left ,right := 0,len(height)-1
    lMax,rMax :=0,0
    total := 0
    for left < right {
        lMax = maxInt(lMax,height[left])
        if lMax  > height[left]{
            total += lMax - height[left]
        }
        rMax = maxInt(rMax,height[right])
        if rMax > height[right] {
            total += rMax - height[right]
        }
        if height[left] < height[right] {
            left++
        }else {
            right--
        }
    }
    return total
}



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

leetCode地址