2021-07-14：接雨水。给定 n 个非负整数表示每个宽度为 1

原创

福大大架构师每日一题

修改于 2021-07-15 10:52:09

3760

修改于 2021-07-15 10:52:09

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
    }
}

执行结果如下：