Skip to main content

42. Trapping Rain Water

分析

/*
累积,预存一下
0,1,0,2,1,0,1,3,2,1,2,1
l 0 0 1 1 2 2 2 2 3 3 3 3 max([i], l[i-1])
r 3 3 3 3 3 3 3 2 2 2 1 0 max([i], r[i+1])
0 0 1 0 1 2 1 0 0 1 0 0
max(0, min(l, r) - [i])
*/

题解

func trap(height []int) int {
length := len(height)

leftMaxHeight, rightMaxHeight := make([]int, length), make([]int, length)
leftMaxHeight[0] = height[0]
rightMaxHeight[length-1] = height[length-1]

for i := 1; i < len(height); i++ {
leftMaxHeight[i] = max(leftMaxHeight[i-1], height[i])
}
for i := length - 2; i >= 0; i-- {
rightMaxHeight[i] = max(rightMaxHeight[i+1], height[i])
}

ans := 0
for i := 1; i < length; i++ {
ans += max(0, min(leftMaxHeight[i], rightMaxHeight[i])-height[i])
}

return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}