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
}
最后编辑: kuteng  文档更新时间: 2021-06-05 10:16   作者:kuteng