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

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

福大大 答案2021-07-14：

左右指针向中间移动。左指针是左边柱子最大高度，右指针是右边柱子最大高度。当左指针小于右指针时，左指针右移；当左指针大于等于右指针时，右指针左移。
时间复杂度：O(N)。
空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {

    height := []int{2, 0, 1, 2}

    ret := trap(height)

    fmt.Println(ret)

}

func trap(height []int) int {

    N := len(height)

    if N <= 2 {

        return 0

    }

    leftMax := height[0]

    rightVal := height[N-1]

    L := 1

    R := N - 2

    ans := 0

    for L <= R {

        if leftMax < rightVal {

            ans += getMax(getMin(leftMax, rightVal)-height[L], 0)

            leftMax = getMax(leftMax, height[L])

            L++

        } else {

            ans += getMax(getMin(leftMax, rightVal)-height[R], 0)

            rightVal = getMax(rightVal, height[R])

            R--

        }

    }

    return ans

}

func getMax(a int, b int) int {

    if a > b {

        return a

    } else {

        return b

    }

}

func getMin(a int, b int) int {

    if a < b {

        return a

    } else {

        return b

    }

}

执行结果如下：

左神java代码

2021-07-14：接雨水。给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。的相关教程结束。