当前位置：首页 > news >正文

22-接雨水

news 2025/9/10 17:39:46

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

方法一：双指针法

思路

使用两个指针 left 和 right 分别指向数组的两端，同时记录左边的最大高度 leftMax 和右边的最大高度 rightMax。在每次迭代中，比较 left 和 right 指向的高度，选择较小的一端进行处理。如果 height[left] < height[right]，则说明左边的柱子可能会接到雨水，此时计算当前位置能接到的雨水量（leftMax - height[left]），并将 left 指针右移一位；否则，说明右边的柱子可能会接到雨水，计算当前位置能接到的雨水量（rightMax - height[right]），并将 right 指针左移一位。重复这个过程，直到 left 和 right 指针相遇。

代码实现

function trap(height: number[]): number {let left = 0;let right = height.length - 1;let leftMax = 0;let rightMax = 0;let result = 0;while (left < right) {if (height[left] < height[right]) {leftMax = Math.max(leftMax, height[left]);result += leftMax - height[left];left++;} else {rightMax = Math.max(rightMax, height[right]);result += rightMax - height[right];right--;}}return result;
}// 示例调用
const height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
const rainWater = trap(height);
console.log("下雨之后能接的雨水:", rainWater);

复杂度分析

时间复杂度：(O(n))，其中 n 是数组 height 的长度。因为只需要遍历一次数组。
空间复杂度：(O(1))，只使用了常数级的额外空间。

方法二：单调栈法

思路

使用一个单调栈来存储柱子的索引。遍历数组，对于每个柱子，如果当前柱子的高度大于栈顶柱子的高度，则说明栈顶柱子可以接到雨水，计算并累加接水量，然后将栈顶元素出栈，重复这个过程，直到栈为空或者当前柱子的高度不大于栈顶柱子的高度。最后将当前柱子的索引入栈。

代码实现

function trap(height: number[]): number {const stack: number[] = [];let result = 0;for (let i = 0; i < height.length; i++) {while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {const top = stack.pop();if (stack.length === 0) {break;}const distance = i - stack[stack.length - 1] - 1;const minHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];result += distance * minHeight;}stack.push(i);}return result;
}// 示例调用
const height2 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
const rainWater2 = trap(height2);
console.log("下雨之后能接的雨水:", rainWater2);