【算法】【难】-直方图水量-动态规划

17.21。HistogramWaterVolume难度：【难】给定一个直方图（也叫直方图），假设有人从上面不断倒水，直方图到底能存多少水？直方图的宽度为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.记录每个元素的高度，从左到右扫描并记录右边的最大高度；
2．记录每个元素的高度，从右向左扫描，记录右边的最大高度；
3．比较左右位置元素，取最小的元素，减去数组当前元素的高度。
从左往右扫描，记录右边最大高度从右往左扫描，记录右边最大高度取最小高度Javascriptvartrap=function(height){letlen=height.lengthif(len===0)return0//记录左边每个矩形的最大高度letleft=Array(len).fill(0)left[0]=height[0]for(leti=1;i=0;--i){right[i]=Math.max(right[i+1],height[i])}//记录结果letret=0for(leti=0;i=0;i--{rightMax[i]=max(rightMax[i+1],height[i])}fmt.Println(leftMax,rightMax)ret:=0对于j:=0;j0{returna}returnb}funcmin(a,bint)int{ifa-b>0{returnb}returna}Typescriptfunctiontrap(height){varlen=height。长度;如果(len===0)返回0；//记录左边每个矩形的最大高度varleft=Array(len);左[0]=高度[0]；对于(vari=1;i=0;--i){right[i]=Math.max(right[i+1],height[i]);}//记录结果varret=0;对于(vari=0;i