直方图的水量
难度:[困难]
给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 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中的每个元素,从左向右扫描并记录右边的最大高度;
2.记录height中的每个元素,从右向左扫描并记录右边的最大高度...;
3.将左右位置元素对比取最小的元素,减去数组当前元素的高度。...从左向右扫描并记录右边的最大高度
从右向左扫描并记录右边的最大高度
取高度最小值
Javascript
var trap = function (height) {
let len = height.length