42. 接雨水¶
题目¶
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1:
输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解释: 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2:
输入: height = [4,2,0,3,2,5]
输出: 9
题解1(双指针)¶
Go
func trap(height []int) int {
left, right := 0, len(height) - 1
leftMax, rightMax := 0, 0
ans := 0
for left < right {
leftMax = max(leftMax, height[left])
rightMax = max(rightMax, height[right])
if leftMax < rightMax {
ans += leftMax - height[left]
left++
} else {
ans += rightMax - height[right]
right--
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Python
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
while left < right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if height[left] < height[right]:
ans += left_max - height[left]
left += 1
else:
ans += right_max - height[right]
right -= 1
return ans
复杂度¶
- 时间复杂度: \(O(n)\)，其中 \(n\) 是 \(height\) 的长度。
- 空间复杂度: \(O(1)\)。
题解2(单调栈)¶
Go
func trap(height []int) (ans int) {
st := []int{}
for i, h := range height {
for len(st) > 0 && h >= height[st[len(st)-1]] {
bottomH := height[st[len(st)-1]]
st = st[:len(st)-1]
if len(st) == 0 {
break
}
left := st[len(st)-1]
dh := min(height[left], h) - bottomH // 面积的高
ans += dh * (i - left - 1)
}
st = append(st, i)
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Python
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
st = []
for i, h in enumerate(height):
while st and h >= height[st[-1]]:
bottom_h = height[st.pop()]
if not st: # len(st) == 0
break
left = st[-1]
dh = min(height[left], h) - bottom_h # 面积的高
ans += dh * (i - left - 1)
st.append(i)
return ans
复杂度¶
- 时间复杂度: \(O(n)\)，其中 \(n\) 是 \(height\) 的长度。
- 空间复杂度: \(O(min(n, U))\)，其中 \(U=max(height)−min(height)+1\)。