LeetCode 42: 接雨水
题目描述：
给定一个包含非负整数的数组 height，每个元素表示一个柱子的高度。每个柱子宽度为 1，计算按此排列的柱子，下雨之后能接多少雨水。
题目分析
接雨水的关键在于：
- 每一个位置能接多少雨水？
一个柱子位置i处能接的雨水量由左右两边的最大高度决定，可以计算为：水量(i) = max(0, min(左侧最大高度, 右侧最大高度) - height[i])。- 如果左侧或右侧的最大高度小于当前柱子高度，那么当前位置无法存水。
- 关键是如何高效地计算每个位置左右两侧的最大高度。
解法 1：暴力解法
思路：
- 遍历数组，对于位置
i，分别计算其左侧和右侧的最大高度：leftMax：从0到i的最大值。rightMax：从i到n-1的最大值。
- 根据公式计算雨水量：
rain[i] = Math.max(0, Math.min(leftMax, rightMax) - height[i]);
模板代码：
class Solution {public int trap(int[] height) {int n = height.length;int totalWater = 0;for (int i = 0; i < n; i++) {int leftMax = 0, rightMax = 0;// 找到左边的最大高度for (int j = 0; j <= i; j++) {leftMax = Math.max(leftMax, height[j]);}// 找到右边的最大高度for (int j = i; j < n; j++) {rightMax = Math.max(rightMax, height[j]);}// 计算当前位置能接的雨水totalWater += Math.max(0, Math.min(leftMax, rightMax) - height[i]);}return totalWater;}
}
时间和空间复杂度：
- 时间复杂度：O(N²)
两层嵌套循环分别计算左右最大高度。 - 空间复杂度：O(1)
没有额外使用数组。
解法 2：预处理 + 动态规划
思路：
- 使用两个数组
leftMax和rightMax分别存储当前位置左侧和右侧的最大高度，使用 动态规划 来提前计算：leftMax[i]：表示从0到i的最大高度：leftMax[i] = Math.max(leftMax[i-1], height[i])。rightMax[i]：表示从i到n-1的最大高度：rightMax[i] = Math.max(rightMax[i+1], height[i])。
- 遍历一次数组，按公式计算雨水量。
模板代码：
class Solution {public int trap(int[] height) {int n = height.length;if (n == 0) return 0;// 预处理左侧和右侧的最大高度int[] leftMax = new int[n];int[] rightMax = new int[n];// 计算左侧最大leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], height[i]);}// 计算右侧最大rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], height[i]);}// 计算雨水总量int totalWater = 0;for (int i = 0; i < n; i++) {totalWater += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);}return totalWater;}
}
时间和空间复杂度：
- 时间复杂度：O(N)
预处理中遍历两次数组，计算leftMax和rightMax，然后最后遍历一次数组。 - 空间复杂度：O(N)
需要额外的leftMax和rightMax数组。
解法 3：双指针
思路：
- 使用两个指针
left和right分别指向数组的两端。 - 维护两个变量
leftMax和rightMax：leftMax：从左向右扫描时左侧的最大高度。rightMax：从右向左扫描时右侧的最大高度。
- 每次比较
leftMax和rightMax：- 如果
leftMax < rightMax，则左指针位置的水量取决于leftMax。 - 否则右指针位置的水量取决于
rightMax。
- 如果
模板代码：
class Solution {public int trap(int[] height) {int left = 0, right = height.length - 1;int leftMax = 0, rightMax = 0;int totalWater = 0;while (left <= right) {if (leftMax < rightMax) {if (height[left] < leftMax) {totalWater += leftMax - height[left];} else {leftMax = height[left];}left++;} else {if (height[right] < rightMax) {totalWater += rightMax - height[right];} else {rightMax = height[right];}right--;}}return totalWater;}
}
时间和空间复杂度：
- 时间复杂度：O(N)
双指针只需要遍历一次数组。 - 空间复杂度：O(1)
没有使用额外的存储空间。
解法 4：单调栈
思路：
- 使用栈来存储柱子的索引。
- 在遍历数组时，维护一个递减栈：
- 如果当前柱子高度小于栈顶柱子，直接入栈。
- 如果当前柱子高度大于栈顶柱子，则「尝试闭合洼地」：
- 栈顶弹出，视为洼地底部。
- 如果栈不为空，计算当前闭合的水量：
高度 = min(左边高度, 右边高度) - 洼地底部高度。 宽度 = 当前索引 - 栈顶索引 - 1。 - 累积水量。
模板代码：
class Solution {public int trap(int[] height) {Stack<Integer> stack = new Stack<>();int totalWater = 0;for (int i = 0; i < height.length; i++) {while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int bottom = stack.pop(); // 弹出洼地底部if (stack.isEmpty()) break; // 如果栈为空，无法形成洼地int left = stack.peek(); // 左边柱子的索引int width = i - left - 1; // 宽度int waterHeight = Math.min(height[i], height[left]) - height[bottom]; // 高度totalWater += width * waterHeight;}stack.push(i);}return totalWater;}
}
时间和空间复杂度：
- 时间复杂度：O(N)
每个柱子仅入栈/出栈一次。 - 空间复杂度：O(N)
栈的空间取决于柱子的数量。
经典变体题目
-
11. 盛最多水的容器：
- 问题：寻找两个柱子之间的最大盛水面积。
- 解法：双指针法（面积 = min(height[left], height[right]) × 宽度）。
-
407. 接雨水 II（3D 版本）：
- 问题：给定一个二维矩阵，表示高度图，计算可以接的最大雨水。
- 解法：使用最小堆 + BFS 模拟水位。
-
接雨水的连续子区间：
- 问题：问「特定区间」的接水量。
- 解法：动态规划或双指针进一步改造。
-
接雨水路径优化：
- 限制接雨水的路径是否能达到最低点，同时积水量递推。
如何快速 AC?
- 优先掌握 双指针法（时间 O(N)，空间 O(1)），适合面试快速实现。
- 在需要更复杂分析时，掌握 动态规划 和 单调栈。
- 对变体题目，坚持递归 + 贪心 + 栈的方法融合应对。