写点什么

LeetCode 题解:42. 接雨水,动态规划,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 25 日
LeetCode题解:42. 接雨水,动态规划,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/trapping-rain-water/



解题思路路:



  1. 假设每个柱子都是一个桶,我们只要知道每个桶的左右桶壁高度的最小值,再减去当前桶底的高度,就可以知道当前桶的装水量,再将每个桶的装水量加起来,即可知道总的装水量。

  2. 使用两次遍历分别查找桶的最高左桶壁和右桶壁。

  3. 例如在查找第i个桶的左桶壁时,maxLeft[i-1]已保存了从0到i-1桶的最大左桶壁,而桶i的左侧是height[i-1],它也是桶壁的候选,因此需要求Math.max(maxLeft[i - 1], height[i - 1])

  4. 由于左右边界都无法装水,因此要设置左右两侧桶的桶壁为0。

  5. 在第三次遍历只要计算桶壁与桶底只差,即可知道每个桶可装水量,将其加总即为结果。



/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let result = 0 // 存储结果
// 创建存储每个捅左边界的数组,设置初始值为0
let maxLeft = new Array(height.length).fill(0);
// 循环生成每个桶的左边界,由于最左和最右的桶没有桶壁,因此无需计算
for (let i = 1; i < maxLeft.length - 1; i++) {
// 当前桶左侧从0到i-1所有桶壁中最高的一个已经被保存,只需要对比其与i-1桶的高度,即可知道桶i的最高左桶壁
maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1])
}
// 创建存储每个捅右边界的数组
let maxRight = new Array(height.length).fill(0)
// 循环生成每个桶的左边界,由于最左和最右的桶没有桶壁,因此无需计算
for (let j = maxRight.length - 2; j > 0; j--) {
// 当前桶右侧从最后到j+1所有桶壁中最高的一个已经被保存,只需要对比其与j+1桶的高度,即可知道桶j的最高右桶壁
maxRight[j] = Math.max(maxRight[j + 1], height[j + 1])
}
// 现在一只每个桶的左桶壁和右桶壁的高度,将其减去当前桶底高度,即为可以装水的高度
for (let k = 0; k < height.length; k++) {
// 每个桶能装水的最大高度,是两个桶壁的最小值
let bucketHeight = Math.min(maxLeft[k], maxRight[k])
// 由于当前bucketHeight保存的是桶壁最大高度,并未计算当前桶底的高度,在此需要判断一下桶壁是否高于桶底
if (bucketHeight > height[k]) {
// 将当前可装水的高度进入结果
result += (bucketHeight - height[k])
}
}
return result
};



发布于: 2020 年 12 月 25 日阅读数: 16
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:42. 接雨水,动态规划,JavaScript,详细注释