双指针
func trap(height []int) int {
n := len(height)
left, right := 0, n - 1
leftMax, rightMax := 0, 0
res := 0
for left <= right {
leftVal := height[left]
rightVal := height[right]
if leftVal > leftMax {
leftMax = leftVal
}
if rightVal > rightMax {
rightMax = rightVal
}
if leftVal < rightVal {
res += min(leftMax, rightMax) - leftVal
left++
} else {
res += min(leftMax, rightMax) - rightVal
right--
}
}
return res
}动态规划
func trap(height []int) int {
n := len(height)
res := 0
if n == 0 {
return res
}
preMax := make([]int, n)
preMax[0] = height[0]
for i := 1; i < n; i++ {
preMax[i] = max(preMax[i - 1], height[i])
}
sufMax := make([]int, n)
sufMax[n - 1] = height[n - 1]
for i := n - 2; i >= 0 ; i-- {
sufMax[i] = max(sufMax[i + 1], height[i])
}
for i := 1; i < n - 1; i++ {
res += max(0, min(preMax[i], sufMax[i]) - height[i])
}
return res
}优化
func trap(height []int) int {
n := len(height)
res := 0
if n == 0 {
return res
}
preMax := make([]int, n)
preMax[0] = height[0]
for i := 1; i < n; i++ {
preMax[i] = max(preMax[i - 1], height[i])
}
sufMax := height[n - 1]
for i := n - 2; i >= 0 ; i-- {
sufMax = max(sufMax, height[i])
res += max(0, min(preMax[i], sufMax) - height[i])
}
return res
}单调栈
单调栈是按照行方向来计算雨水
func trap(height []int) int {
n := len(height)
res := 0
stack := []int{}
for right := 0; right < n; right++ {
for len(stack) > 0 && height[stack[len(stack) - 1]] < height[right] {
cur := height[stack[len(stack) - 1]]
stack = stack[:len(stack) - 1]
if len(stack) == 0 {
break
}
left := stack[len(stack) - 1]
res += (right - left - 1) * (min(height[left], height[right]) - cur)
}
stack = append(stack, right)
}
return res
}