17.21. 直方图的水量
难度:[艰难]
给定一个直方图(也称柱状图)，假如有人从下面源源不断地倒水，最初直方图能存多少水量?直方图的宽度为 1。
下面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 示意的直方图，在这种状况下，能够接 6 个单位的水（蓝色局部示意水）。 感激 Marcos 奉献此图。
示例:
输出: [0,1,0,2,1,0,1,3,2,1,2,1]输入: 6【思路】动静布局
1.记录height中的每个元素，从左向右扫描并记录左边的最大高度;<br/>
2.记录height中的每个元素，从右向左扫描并记录左边的最大高度;<br/>
3.将左右地位元素对比取最小的元素，减去数组以后元素的高度。<br/>
从左向右扫描并记录左边的最大高度
从右向左扫描并记录左边的最大高度
取高度最小值
Javascript
var trap = function (height) { let len = height.length if (len === 0) return 0 //记录右边每个矩形最大高度 let left = Array(len).fill(0) left[0] = height[0] for (let i = 1; i < len; ++i) { left[i] = Math.max(left[i - 1], height[i]) } //记录左边每个矩形最大高度 let right = Array(len).fill(0) right[len - 1] = height[len - 1] for (let i = len - 2; i >= 0; --i) { right[i] = Math.max(right[i + 1], height[i]) } //记录后果 let ret = 0 for (let i = 0; i < len; ++i) { //左右比照取最小边界，减去以后矩形高度 ret += Math.min(left[i], right[i]) - height[i] } return ret};go
func trap(height []int) int { n := len(height) if n == 0 { return 0 } //记录右边每个元素最大高度 leftMax := make([]int, n) leftMax[0] = height[0] for i := 1; i < n; i++ { leftMax[i] = max(leftMax[i-1], height[i]) } //记录右边每个元素最大高度 rightMax := make([]int, n) rightMax[n-1] = height[n-1] for i := n - 2; i >= 0; i-- { rightMax[i] = max(rightMax[i+1], height[i]) } fmt.Println(leftMax, rightMax) ret := 0 for j := 0; j < n; j++ { ret += (min(leftMax[j], rightMax[j]) - height[j]) } return ret}//因为Go语言外面没有max(),min()须要本人实现一个func max(a, b int) int { if a-b > 0 { return a } return b}func min(a, b int) int { if a-b > 0 { return b } return a}Typescript
function trap(height) { var len = height.length; if (len === 0) return 0; //记录右边每个矩形最大高度 var left = Array(len); left[0] = height[0]; for (var i = 1; i < len; ++i) { left[i] = Math.max(left[i - 1], height[i]); } //记录左边每个矩形最大高度 var right = Array(len); right[len - 1] = height[len - 1]; for (var i = len - 2; i >= 0; --i) { right[i] = Math.max(right[i + 1], height[i]); } //记录后果 var ret = 0; for (var i = 0; i < len; ++i) { //左右比照取最小边界，减去以后矩形高度 ret += Math.min(left[i], right[i]) - height[i]; } return ret;}python
class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ if not height: return 0 # 数组长度 n = len(height) # 记录右边每个矩形最大高度 left = [0]*n left[0] = height[0] for i in range(1,n): left[i] = max(left[i - 1], height[i]) # 记录左边每个矩形最大高度 right = [0]*n right[n - 1] = height[n - 1] for i in range(n-2,-1,-1): right[i] = max(right[i + 1], height[i]) # 记录后果 ret = sum(min(left[i], right[i]) - height[i] for i in range(n)) return ret持续加油！哦里给