写点什么

LeetCode 题解:42. 接雨水,暴力法,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 24 日
LeetCode题解:42. 接雨水,暴力法,JavaScript,详细注释

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



解题思路:



  1. 把每个柱子当做一个水桶,它能装水的最大值,即为它桶壁的最小值。

  2. 第一步遍历height,每一项就是当前水桶的底部高度。

  3. 第二步以当前索引为起点,左右高度的起始值就是当前桶底的高度,分别向左和向右查找最大高度,对应的就是水桶的左右两个桶壁。

  4. 第三步是取左右桶壁的最小值,再与桶底的高度相减,就是当前水桶能装的最多水量。

  5. 重复前三个步骤,将水量都加入结果,就可以得到总共能装的最多水量。



/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let result = 0; // 储存结果
// 枚举每个柱子,查找每个柱子可以接的雨水高度
for (let i = 0; i < height.length; i++) {
let left = 0; // 保存左边界的高度
let right = 0; // 保存右边界的高度
// 第一步遍历时,左右边界就被赋值为桶底高度,即height[i]
// 枚举查找左边界的最大高度
for (let j = i; j >= 0; j--) {
left = Math.max(left, height[j]);
}
// 枚举查找右边界的最大高度
for (let k = i; k < height.length; k++) {
right = Math.max(right, height[k]);
}
// 一个水桶的最短桶壁就是它能装的最大水高度,在这里就是左右边界的最小值。
// height[i]即为当前水桶的底边
// 当前水桶能装的最大水量,就是左右边界的最小值减去当前底边高度
// 最后将当前水桶的装水量计入结果
result += Math.min(left, right) - height[i]
}
return result
};



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

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:42. 接雨水,暴力法,JavaScript,详细注释