题目:
给定 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
提示:
题解
将整个列表按照最大值 maxV 分成两部分,左边以及右边的所有的值都不可能超过最大值 maxV。
对于所有的左边值来说,可以将最大值 maxV 作为所有蓄水池的右边界。
而蓄水池的左边界则是从左到右遍历到当前值是的最大值。
最终的水平面将取决于值较小的边界,则为左边界。
def trap(height):maxI = np.argmax(height).flatten()[0]tr = i = 0for j in range(1, maxI):if height[i] > height[j]:tr += height[i] - height[j]else:i = ji = len(height) - 1for j in range(len(height) - 2, maxI, -1):if height[i] > height[j]:tr += height[i] - height[j]else:i = jreturn tr