LeetCode 42.接雨水
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)），适合面试快速实现。
- 在需要更复杂分析时，掌握 动态规划 和 单调栈。
- 对变体题目，坚持递归 + 贪心 + 栈的方法融合应对。