题目描述 复制
给定
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 个单位的雨水（蓝色部分表示雨水）。
输入
0,1,0,2,1,0,1,3,2,1,2,1
输出
6
提示
也可以使用动态规划的方法提升算法效率，动态规划的代码参考如下：
n = len(height)
maxleft = [0] * n
maxright = [0] * n
ans = 0
# 初始化
maxleft[0] = height[0]
maxright[n-1] = height[n-1]
# 分别存储左边和右边最高的柱子高度
for i in range(1,n):
maxleft[i] = max(height[i],maxleft[i-1])
for j in range(n-2,-1,-1):
maxright[j] = max(height[j],maxright[j+1])
# 一趟遍历，比较每个位置可以存储多少水
for i in range(n):
if min(maxleft[i],maxright[i]) > height[i]:
ans += min(maxleft[i],maxright[i]) - height[i]
print(ans)
n = len(height)
maxleft = [0] * n
maxright = [0] * n
ans = 0
# 初始化
maxleft[0] = height[0]
maxright[n-1] = height[n-1]
# 分别存储左边和右边最高的柱子高度
for i in range(1,n):
maxleft[i] = max(height[i],maxleft[i-1])
for j in range(n-2,-1,-1):
maxright[j] = max(height[j],maxright[j+1])
# 一趟遍历，比较每个位置可以存储多少水
for i in range(n):
if min(maxleft[i],maxright[i]) > height[i]:
ans += min(maxleft[i],maxright[i]) - height[i]
print(ans)
代码填空 复制
height = list(map(int,input().split(",")))
ans = 0
for i in range(len(height)):
max_left = 0
max_right = 0
# 寻找 max_left
for j in range(0,i):
max_left = max(max_left,height[j])
# 寻找 max_right
for j in range(i,len(height)):
max_right = __________
if __________:
ans += min(max_left,max_right) - height[i]
print(ans)