问题:
给定 n 个非负整数表示每个宽度为 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 个单位的雨水(蓝色部分表示雨水)。
思路和代码:
class Solution:
def trap(self, height: List[int]) -> int:
# 对于一个能存水的地方,它的起始位置和终止位置需要满足
# 在它的左边和右边都有比它高的柱子
# 那么如何找到左边和右边比它高的柱子呢
# 那么可以用两个数组保存在i位置的左边最高柱子和右边的最高柱子的高度
# 在位置i的存水数量就是water_tmp = min(left_max_height, right_max_height)
# 如果当前的柱子低于上面存水的数量,那么就可以存水water_tmp - height[i]
L = len(height)
left_max_height_list = [0] * L
right_max_height_list = [0] * L
left_max_height = 0 # 记录左边最大值
right_max_height = 0 # 记录右边最大值
for i in range(1, L):
left_max_height_list[i] = left_max_height = max(left_max_height, height[i - 1])
right_max_height_list[L - 1 - i] = right_max_height = max(right_max_height, height[L - i])
water = 0
for i in range(1, L):
water_tmp = min(left_max_height_list[i], right_max_height_list[i])
if water_tmp > height[i]:
water += water_tmp - height[i]
return water
文章评论