云南网站设计模板广州知名网站

题目：

给定 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