接雨水（Trapping Rain Water）是 LeetCode 上最经典的算法题目之一，也是面试中的高频考点。给定一排高度不等的柱子，计算下雨后能积多少水。这个问题看似简单，却能从暴力解法逐步优化到仅需一次遍历的双指针法，完美展示了算法设计的演进思维。
问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
在这个例子中，柱子之间形成了若干凹陷区域，雨水会积聚在凹陷中。每个位置能接的雨水量，取决于其左侧最高柱子和右侧最高柱子的较小值。
核心思路：每个位置能接多少水？
对于位置 i，设其左侧最高柱子高度为 leftMax，右侧最高柱子高度为 rightMax。该位置能接的雨水量为：
water[i] = max(0, min(leftMax, rightMax) - height[i])
只有当 min(leftMax, rightMax) > height[i] 时，该位置才能积水。这个公式是整个问题的基础，所有解法都是围绕如何高效计算每个位置的 leftMax 和 rightMax 展开的。
方法一：暴力解法
最直观的想法是：对于每个位置，分别向左扫描找最高柱子，向右扫描找最高柱子，然后计算积水。
public class TrappingRainWater {
/**
* 暴力解法：对每个位置，分别向左右扫描找最高柱子
* 时间复杂度：O(n²)，空间复杂度：O(1)
*/
public int trapBruteForce(int[] height) {
int n = height.length;
int totalWater = 0;
// 第一个和最后一个位置不可能积水（没有两侧）
for (int i = 1; i < n - 1; i++) {
int leftMax = 0;
int 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.min(leftMax, rightMax) - height[i];
}
return totalWater;
}
}
暴力解法虽然思路简单，但时间复杂度为 O(n²)，对于大规模数据会超时。其瓶颈在于对每个位置都重复扫描左右区间。
方法二：动态规划（预处理优化）
观察暴力解法，我们发现每个位置的 leftMax 和 rightMax 被重复计算了很多次。可以用两个数组预先存储每个位置的左侧最高和右侧最高柱子高度。
/**
* 动态规划解法：预处理每个位置的leftMax和rightMax
* 时间复杂度：O(n)，空间复杂度：O(n)
*/
public int trapDP(int[] height) {
int n = height.length;
if (n == 0) return 0;
// leftMax[i] 表示位置i（含）左侧的最高柱子高度
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// rightMax[i] 表示位置i（含）右侧的最高柱子高度
int[] rightMax = new int[n];
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.min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
动态规划解法将时间复杂度降到了 O(n)，但需要 O(n) 的额外空间存储两个辅助数组。对于空间敏感的场景，还有优化空间。
方法三：双指针（空间优化到 O(1)）
双指针法是接雨水问题的最优解，时间复杂度 O(n)，空间复杂度 O(1)。其核心思想是：用两个指针从两端向中间移动，维护当前已见的左右最高柱高度。
/**
* 双指针解法：从两端向中间移动，维护左右最高柱高度
* 时间复杂度：O(n)，空间复杂度：O(1)
*/
public int trapTwoPointers(int[] height) {
int n = height.length;
if (n == 0) return 0;
int left = 0; // 左指针
int right = n - 1; // 右指针
int leftMax = 0; // 左指针已遍历区域的最大高度
int rightMax = 0; // 右指针已遍历区域的最大高度
int totalWater = 0;
while (left < right) {
// 移动高度较小一侧的指针，因为积水高度由短板决定
if (height[left] < height[right]) {
// 处理左指针位置
if (height[left] >= leftMax) {
// 当前柱子高于leftMax，更新leftMax，无法积水
leftMax = height[left];
} else {
// 当前柱子低于leftMax，可以积水
// 右侧一定有更高的柱子（因为right指针位置更高）
// 所以积水量由leftMax决定
totalWater += leftMax - height[left];
}
left++;
} else {
// 处理右指针位置
if (height[right] >= rightMax) {
// 当前柱子高于rightMax，更新rightMax，无法积水
rightMax = height[right];
} else {
// 当前柱子低于rightMax，可以积水
// 左侧一定有更高的柱子（因为left指针位置更高或相等）
totalWater += rightMax - height[right];
}
right--;
}
}
return totalWater;
}
双指针的关键理解
为什么移动高度较小一侧的指针？
- 假设
height[left] < height[right]，那么位置left的右侧最高柱子一定>= height[right] > height[left] - 因此位置
left的积水高度由leftMax决定（右侧一定够高） - 同理，当
height[right] <= height[left]时，位置right的积水高度由rightMax决定
方法四：单调栈
单调栈是另一种优雅的解法，尤其适合处理 “找下一个更大/更小元素” 的场景。维护一个单调递减栈，当遇到更高的柱子时，栈顶元素就可以与当前柱子形成一个凹槽来积水。
/**
* 单调栈解法：维护单调递减栈，遇到更高柱子时计算积水
* 时间复杂度：O(n)，空间复杂度：O(n)
*/
public int trapMonotonicStack(int[] height) {
int n = height.length;
if (n == 0) return 0;
// 栈中存储的是柱子的下标，对应高度单调递减
java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
int totalWater = 0;
for (int i = 0; i < n; i++) {
// 当前柱子高于栈顶，可以形成凹槽
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
// 弹出栈顶作为凹槽底部
int bottom = stack.pop();
// 栈为空说明没有左边界，无法积水
if (stack.isEmpty()) break;
// 凹槽的左边界是新的栈顶
int left = stack.peek();
// 凹槽的右边界是当前柱子
int right = i;
// 计算凹槽宽度
int width = right - left - 1;
// 计算积水高度（由左右边界较小值决定）
int waterHeight = Math.min(height[left], height[right]) - height[bottom];
totalWater += width * waterHeight;
}
stack.push(i);
}
return totalWater;
}
单调栈的思路解析
单调栈解法不是按位置计算积水，而是按 “层” 计算积水。每次遇到更高的右边界时，就将栈中的低洼区域 “填平” 一层。这种方法在处理多维接雨水问题（如接雨水 II）时具有天然的优势。
完整可运行代码
import java.util.ArrayDeque;
import java.util.Deque;
/**
* 接雨水问题：多种解法的完整实现
*
* 问题描述：给定n个非负整数表示每个宽度为1的柱子的高度图，
* 计算按此排列的柱子下雨之后能接多少雨水。
*/
public class TrappingRainWater {
public static void main(String[] args) {
TrappingRainWater solution = new TrappingRainWater();
// 测试用例
int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println("输入: " + java.util.Arrays.toString(height));
System.out.println("暴力解法结果: " + solution.trapBruteForce(height));
System.out.println("动态规划结果: " + solution.trapDP(height));
System.out.println("双指针结果: " + solution.trapTwoPointers(height));
System.out.println("单调栈结果: " + solution.trapMonotonicStack(height));
// 额外测试：空数组和单元素
System.out.println("\n空数组测试结果: " + solution.trapTwoPointers(new int[]{}));
System.out.println("单元素测试结果: " + solution.trapTwoPointers(new int[]{5}));
// 性能测试
System.out.println("\n=== 性能测试（100000个元素）===");
int[] largeArray = new int[100000];
java.util.Random random = new java.util.Random(42);
for (int i = 0; i < largeArray.length; i++) {
largeArray[i] = random.nextInt(100000);
}
long start = System.currentTimeMillis();
solution.trapDP(largeArray);
System.out.println("DP解法耗时: " + (System.currentTimeMillis() - start) + "ms");
start = System.currentTimeMillis();
solution.trapTwoPointers(largeArray);
System.out.println("双指针解法耗时: " + (System.currentTimeMillis() - start) + "ms");
start = System.currentTimeMillis();
solution.trapMonotonicStack(largeArray);
System.out.println("单调栈解法耗时: " + (System.currentTimeMillis() - start) + "ms");
}
/**
* 暴力解法：对每个位置，分别向左右扫描找最高柱子
*/
public int trapBruteForce(int[] height) {
int n = height.length;
int totalWater = 0;
for (int i = 1; i < n - 1; 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.min(leftMax, rightMax) - height[i];
}
return totalWater;
}
/**
* 动态规划解法：预处理每个位置的leftMax和rightMax
*/
public int trapDP(int[] height) {
int n = height.length;
if (n == 0) return 0;
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
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.min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
/**
* 双指针解法：最优解，O(n)时间O(1)空间
*/
public int trapTwoPointers(int[] height) {
int n = height.length;
if (n == 0) return 0;
int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int totalWater = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
totalWater += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
totalWater += rightMax - height[right];
}
right--;
}
}
return totalWater;
}
/**
* 单调栈解法：按层计算积水
*/
public int trapMonotonicStack(int[] height) {
int n = height.length;
if (n == 0) return 0;
Deque<Integer> stack = new ArrayDeque<>();
int totalWater = 0;
for (int i = 0; i < n; 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[left], height[i]) - height[bottom];
totalWater += width * waterHeight;
}
stack.push(i);
}
return totalWater;
}
}
复杂度对比
| 解法 | 时间复杂度 | 空间复杂度 | 核心思想 |
|---|---|---|---|
| 暴力解法 | O(n²) | O(1) | 对每个位置扫描左右区间 |
| 动态规划 | O(n) | O(n) | 预处理左右最高数组 |
| 双指针 | O(n) | O(1) | 两端向中间移动，维护左右最高 |
| 单调栈 | O(n) | O(n) | 维护递减栈，遇到高柱计算积水 |
双指针法是面试中最推荐的解法，因为它同时达到了最优的时间和空间复杂度。单调栈法则在思想上更有启发性，其 “按层填平” 的思路可以自然地推广到二维接雨水问题。
总结
接雨水问题虽然只是一个 “接水” 的模拟，但它涵盖了从暴力到 DP、再到双指针和单调栈的完整优化路径。学习这个问题，不仅能掌握四种经典算法技巧，更能体会到算法设计的核心思想：识别重复计算 → 用预处理或增量维护消除冗余 → 在空间上做进一步优化。
在实际工程中，这种 “先想通暴力解法，再逐步优化” 的思路同样适用。理解每个优化步骤背后的原理，比背诵代码更重要。
