曼斯特(北京)网站建设公司,网页回合制游戏排行榜,黄石公司做网站,seo优化评论题目#xff1a;
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;6 解释#xff1a;上面是由数组[0,1,0,2…题目
给定 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
