原题地址：接雨水
给定 n 个非负整数表示每个宽度为 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
暴力计算
根据题意可知，每个格子可以接的水量是由它两边的柱子高度与当前格子的高度之差决定。既然如此，我们对每个格子就可以分别求出它两边柱子的最大高度，然后直接计算这个格子可以接多少水，再将所有格子可以接的水累加即可。
具体的实现代码如下：
/**
* @param {number[]} height
* @return {number}
*/
const trap1 = function(height) {
// 要储水最少要有3个格子
if (height.length < 3) {
return 0;
}
let result = 0;
for (let i = 1; i < height.length - 1; i ++) {
let [left, right] = [i, i]; // 计算左右两边柱子高度的指针
let [maxLeft, maxRight] = [height[i], height[i]]; // 左右两边柱子的最大高度
// 分别计算左右两边柱子的最大高度
while (left > 0) {
left --;
maxLeft = Math.max(maxLeft, height[left]);
}
while (right < height.length - 1) {
right ++;
maxRight = Math.max(maxRight, height[right])
}
// 根据木桶原理，当前柱子能接的水量由左右柱子中较小的一个决定
result += Math.min(maxLeft, maxRight) - height[i];
}
return result;
};
测试：
let start = new Date();
const test = trap1;
console.log(test([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(test([5,2,1,2,1,5])); // 14
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度： 找到每个柱子需要一轮遍历，对每个柱子计算左右两边柱子高度的最大值又需要一次遍历，双重遍历，时间复杂度为$O(n^2)$
空间复杂度： 常数级额外空间，空间复杂度为$O(1)$
动态规划
暴力计算中我们求解每个柱子左右两边柱子最大高度都需要一次遍历，实际上都是在重复计算。我们只需要分别从左右两边各遍历一次，就能知道每个柱子左右两边柱子高度的最大值并存储起来，然后一轮遍历就可以计算出总的储水值。
具体实现如下:
/**
* @param {number[]} height
* @return {number}
*/
const trap2 = function(height) {
if (height.length < 3) {
return 0;
}
// 计算各柱子左边柱子的最大值，初始值为柱子本身的高度
let maxLeft = [...height];
for (let i = 1; i < height.length; i ++) {
// 如果maxLeft[i - 1]为n,就说明如果不包括maxLeft[i]，当前柱子左边的最大高度也是n
maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
}
// 计算各柱子右边柱子的最大值，初始值为柱子本身的高度
let maxRight = [...height];
for (let i = height.length - 2; i >= 0; i --) {
maxRight[i] = Math.max(maxRight[i + 1], height[i]);
}
// 与暴力计算一样，计算每个柱子的储水值
let result = 0;
for (let i = 0; i < height.length; i ++) {
result += Math.min(maxLeft[i], maxRight[i]) - height[i]
}
return result;
};
测试：
let start = new Date();
const test = trap2;
console.log(test([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(test([5,2,1,2,1,5])); // 14
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 总共进行了三次遍历，但没有嵌套遍历，所以时间复杂度为$O(3n)=O(n)$
空间复杂度： 需要两个数组分别存储再次遍历得到的最大值，空间复杂度为$O(2n)=O(n)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 9,2019