42. 接雨水

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

rainwatertrap.png

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

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路分析

可记录每个位置左边最大和右边最大，其中0位置无左边最大，length位置无右边最大；
注意左边最大和右边最大都不如自己本身大的情况；

解题

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

func Min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func trap(height []int) int {
    length := len(height)
    left := make([]int, length)
    right := make([]int, length)
    for i := 1; i < length; i++ {
        left[i] = Max(left[i-1], height[i-1])
    }
    for i := length - 2; i >= 0; i-- {
        right[i] = Max(right[i+1], height[i+1])
    }
    res := 0
    for i := 0; i < length; i++ {
        hwm := Min(left[i], right[i])
        res += Max(0, hwm-height[i])
    }
    return res
}

附：

为什么Golang中没有整数的max / min函数？
Golang中没有提供max / min函数来比较两个或多个整数的最大值/最小值。用其他语言，这些功能作为核心库功能的一部分提供。实际上，Golang在math包中提供了max / min函数，但它们用于比较float64数据类型。这两个功能的为：

math.Min(float64, float64) float64
math.Max(float64, float64) float64

Golang提供用于比较float64数字的max / min函数的原因是，对于大多数开发人员而言，浮点数的处理非常复杂，鉴于计算机体系结构的本质，比较两个浮点数并不是那么简单。如果开发人员实施自己的最大/最小浮点数逻辑，为避免给开发的应用程序带来麻烦，Golang中math包将其作为内置函数提供给他们。
对于int / int64数据类型，max / min逻辑相对容易实现。具有基本技能的开发人员可以轻松地为整数类型实现这两个功能。

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

func Min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

另外，为了使Golang尽可能简洁和整洁，Golang中不支持泛型。由于为float64数据类型实现了最大/最小，因此不能在同一数学包中实现具有相同名称但具有不同参数类型的函数。因此，以下两个不能存在于同一package中。

math.Max(float64, float64) float64
math.Max(int64, int64) int64

此设计注意事项符合Golang的设计原则，使Golang尽可能简洁明了。