42_trapping_rain_water

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

代码参考：

package main

import "fmt"

func main() {
    fmt.Println(trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})) // 6
}

func trap(height []int) int {
    area := 0
    l, r := 0, len(height)-1
    lTop, rTop := 0, 0

    for l <= r {
        lTop = max(height[l], lTop)
        rTop = max(height[r], rTop)
        if lTop < rTop {
            area += lTop - height[l] // 右侧更高些，往右侧走。一边向右移，一边计算高度差来累计面积（最高点处高度差为 0）
            l++
        } else {
            area += rTop - height[r] // 向左侧移，用目前右侧最高高度来计算高度差，累计面积
            r--
        }
    }
    return area
}

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