接雨水。给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
左右指针向中间移动。左指针是左边柱子最大高度，右指针是右边柱子最大高度。当左指针小于右指针时，左指针右移；当左指针大于等于右指针时，右指针左移。
时间复杂度：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
}
}执行结果如下：
