85 lines
2.9 KiB
JavaScript
85 lines
2.9 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {number[]} height
|
||
* @return {number}
|
||
*/
|
||
const trap = function (height) {
|
||
|
||
};
|
||
|
||
/*
|
||
观察可以发现：我们只需要把每个位置上的水量加起来，就是总水量了，每个位置上的水量取决于它左右两侧最高柱子较低的那个柱子减去
|
||
自身的高度，所以我们只需要定义两个数组leftMax和rightMax 来保存当前柱子左边和右边的最高柱子，之后再统计所有水量
|
||
*/
|
||
|
||
function f1(height) {
|
||
// 如果数组为空或者长度小于3，无法接水，直接返回0
|
||
if (height.length < 3) return 0;
|
||
|
||
const n = height.length;
|
||
// 创建两个数组，分别存储左边和右边的最大高度
|
||
const leftMax = new Array(n);
|
||
const rightMax = new Array(n);
|
||
|
||
// 初始化左边最大高度数组
|
||
// leftMax[0] = height[0];
|
||
[leftMax[0]] = height;
|
||
for (let i = 1; i < n; i++) {
|
||
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
|
||
}
|
||
|
||
// 初始化右边最大高度数组
|
||
rightMax[n - 1] = height[n - 1];
|
||
for (let i = n - 2; i >= 0; i--) {
|
||
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
|
||
}
|
||
|
||
let water = 0;
|
||
|
||
// 计算每个位置能够接的水量
|
||
for (let i = 0; i < n; i++) {
|
||
// 能接的水量 = 该位置的左边最大高度与右边最大高度中的较小值减去该位置的高度
|
||
water += Math.min(leftMax[i], rightMax[i]) - height[i];
|
||
}
|
||
|
||
return water;
|
||
}
|
||
|
||
/*
|
||
方法2，一个位置要想接住水，它的左右两侧必须比他高，不光左右两侧有多远，只要比他高就一定能接住雨水，但是这个接住的雨水应该是
|
||
多少，应该由谁决定，经过观察也很好发现，其实就是左右两侧较低的那一边，如果一个位置左侧有一个最大的柱子，右侧也有最大的柱子，那么
|
||
它的接水量就是左右两侧较小的那一个减去当前柱子的高度，中间柱子的高度不影响这一位置的接水量（仔细思考这一点）
|
||
*/
|
||
|
||
function f2(height) {
|
||
let left = 0; let
|
||
right = height.length - 1;
|
||
let leftMax = 0; let
|
||
rightMax = 0;
|
||
let water = 0;
|
||
|
||
// 双指针向中间靠拢
|
||
while (left < right) {
|
||
// 优化：先判断哪个边界较低，频繁出现的情况优先处理
|
||
if (height[left] < height[right]) {
|
||
// 左边较低，更新左边的最大高度
|
||
if (height[left] >= leftMax) {
|
||
leftMax = height[left]; // 更新左边的最大高度
|
||
} else {
|
||
water += leftMax - height[left]; // 计算水量
|
||
}
|
||
left++; // 向右移动
|
||
} else {
|
||
// 右边较低或相等，更新右边的最大高度
|
||
if (height[right] >= rightMax) {
|
||
rightMax = height[right]; // 更新右边的最大高度
|
||
} else {
|
||
water += rightMax - height[right]; // 计算水量
|
||
}
|
||
right--; // 向左移动
|
||
}
|
||
}
|
||
|
||
return water; // 返回总的接水量
|
||
}
|