2021-07-14：接雨水。给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
生活随笔
收集整理的這篇文章主要介紹了
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 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何选择JavaScript构建工具之B
- 下一篇： weblogic