接雨水
题目链接
题目
给定一个整数数组 height
表示柱子的高度,其中宽度为 1,计算柱子之间能够接住多少雨水。
思路
使用双指针方法解决此问题。通过从两端向中间遍历数组,并更新左右两侧的最大高度,可以高效计算每个位置的存水量。双指针法利用了当前柱子的高度和左右两侧最大高度的对比,决定了水的存储量。
解题方法
-
初始化指针和变量:
left
和right
指针分别指向数组的两端(即0
和height.length - 1
)。leftMax
和rightMax
分别记录从左到右和从右到左扫描时遇到的最大高度。result
用于累加最终计算出的雨水量。
-
遍历数组:
- 使用
while (left < right)
循环,遍历数组,直到left
和right
指针相遇。 - 在每 次循环中,比较
leftMax
和rightMax
的值:- 左侧较低 (
leftMax < rightMax
):- 向右移动
left
指针 (left++
)。 - 更新
leftMax
为leftMax
和height[left]
中的较大值,表示更新左侧遇到的最大高度。 - 计算当前位置的雨水量,即
leftMax - height[left]
,并将其加到result
中。如果当前高度height[left]
小于leftMax
,说明当前位置能够接到雨水。
- 向右移动
- 右侧较低或相等 (
leftMax >= rightMax
):- 向左移动
right
指针 (right--
)。 - 更新
rightMax
为rightMax
和height[right]
中的较大值,表示更新右侧遇到的最大高度。 - 计算当前位置的雨水量,即
rightMax - height[right]
,并将其加到result
中。如果当前高度height[right]
小于rightMax
,说明当前位置能够接到雨水。
- 向左移动
- 左侧较低 (
- 使用
-
返回结果:
result
存储了整个数组中可以接到的总雨水量。
代码
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
if (height.length === 0) return 0;
let left = 0, right = height.length - 1;
let result = 0, leftMax = height[left], rightMax = height[right];
while (left < right) {
if (leftMax < rightMax) {
left++;
leftMax = Math.max(leftMax, height[left]);
result += leftMax - height[left];
} else {
right--;
rightMax = Math.max(rightMax, height[right]);
result += rightMax - height[right];
}
}
return result;
};
复杂度
- 时间复杂度: ,其中 是数组的长度。双指针法确保每个位置只处理一次。
- 空间复杂度: ,只使用了固定的额外空间。