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))，在最坏情况下，栈中可能会存储所有的柱子索引。

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