22-接雨水

给定 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);

复杂度分析

• 时间复杂度：(O(n))，其中 n 是数组 height 的长度。虽然有一个嵌套的 while 循环，但每个元素最多入栈和出栈一次，所以总的时间复杂度仍然是 (O(n))。
• 空间复杂度：(O(n))，在最坏情况下，栈中可能会存储所有的柱子索引。

综上所述，双指针法和单调栈法都能有效地解决接雨水问题，双指针法的代码相对简单，空间复杂度较低；单调栈法的思路相对复杂一些，但也能清晰地处理接雨水的逻辑。