跳至主要內容

接雨水：单调栈、双指针、前缀数组四种解法全景对比

老张2026/4/30大约 11 分钟

接雨水：单调栈、双指针、前缀数组四种解法全景对比

适读人群：Java 开发者、冲击大厂算法面试的工程师 | 阅读时长：约25分钟 | 难度：Hard

开篇故事

接雨水是我面试别人时出现频率最高的一道题，没有之一。这几年我大概在面试里出了七八十次这道题，见过太多候选人的各种反应：有人一眼看出双指针、有人绞尽脑汁写出了前缀数组、有人在纸上画了半天想清楚了单调栈，也有人三十分钟愣是一个方法都想不出来。

印象最深的是一个候选人，技术背景非常扎实，系统设计做得很好，但接雨水只写了个暴力解。我追问有没有更优的，他说："我知道可以用动态规划，但现在想不到怎么推。"当时我心里有点遗憾——这道题如果提前练过，两种以上的解法是可以直接背下来的。

后来我复盘了一下：接雨水之所以出现频率高，是因为它能考察多种算法技能——动态规划、双指针、单调栈——在一道题里全考到了。而且每种解法都有其思维深度，不是简单套模板就能写出来的。

这道题我自己也摔过跤。第一次刷是 2019 年，想明白了暴力和前缀数组，但双指针想了一个多小时才真正理解为什么可以用。单调栈的解法更是两年后才搞透的。今天把我对这四种解法的全部理解都写出来，算是给自己一个交代。

一、题目解析

LeetCode 42. 接雨水（Trapping Rain Water）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入输出示例：

示例 1（经典情况）：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是高度图，可以接 6 单位的雨水（蓝色部分）

示例 2（W 形）：

输入：height = [4,2,0,3,2,5]
输出：9

边界情况 3（单调递增，无法接水）：

输入：height = [1,2,3,4,5]
输出：0

边界情况 4（全部相同高度，无法接水）：

输入：height = [3,3,3,3]
输出：0

边界情况 5（只有两根柱子）：

输入：height = [3,0,3]
输出：3
解释：中间凹陷，能接 3 单位水

考察的核心知识点：

  • 每个位置能接多少水由其左右最高柱决定（木桶原理）
  • 前缀/后缀最大值数组
  • 双指针的收缩原理
  • 单调栈维护"未确定"的边界

二、解法一：暴力解法

思路分析

对于每个位置 i，能接的雨水量 = min(左边最高柱, 右边最高柱) - height[i]。

这是这道题最核心的数学洞察：位置 i 处的水位不超过左边最高柱和右边最高柱中较小的那个（木桶原理）。如果水位超过较小的一边，水就从那边溢出去了。

暴力：对每个 i，向左遍历找左边最高柱（O(n)），向右遍历找右边最高柱（O(n)），计算当前位置的接水量，累加。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int total = 0;
        
        // 枚举每个位置
        for (int i = 1; i < n - 1; i++) {  // 首尾不能接水
            // 找左边最高柱
            int maxLeft = 0;
            for (int j = 0; j < i; j++) {
                maxLeft = Math.max(maxLeft, height[j]);
            }
            
            // 找右边最高柱
            int maxRight = 0;
            for (int j = i + 1; j < n; j++) {
                maxRight = Math.max(maxRight, height[j]);
            }
            
            // 当前位置的接水量（如果负数说明是凸起，接水量为0）
            int water = Math.min(maxLeft, maxRight) - height[i];
            if (water > 0) {
                total += water;
            }
        }
        
        return total;
    }
}

时间复杂度：O(n²)，每个位置都做两次 O(n) 的扫描。

空间复杂度：O(1)。

三、解法二：前缀/后缀最大值数组（O(n)，空间 O(n)）

优化思路

暴力的重复计算：对每个 i，都重新扫描左边和右边。但实际上左边最大值和右边最大值可以提前预计算，存入数组，直接查询。

预处理：

  • leftMax[i] = height[0..i] 中的最大值（包括 i 自身）
  • rightMax[i] = height[i..n-1] 中的最大值（包括 i 自身）

注意：leftMax[i] 包含 height[i] 自身，所以计算接水量时是 min(leftMax[i], rightMax[i]) - height[i]，这个值保证非负（因为 leftMax[i] >= height[i] 且 rightMax[i] >= height[i]）。

class Solution {
    public int trap(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 total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return total;
    }
}

时间复杂度：O(n)，三次线性扫描。

空间复杂度：O(n)，两个辅助数组。

四、解法三：双指针（O(n)，空间 O(1)）

核心洞见

前缀数组已经是 O(n) 时间了，但需要 O(n) 额外空间。能不能把空间降到 O(1)？

双指针的核心洞察：

用 left 和 right 两个指针从两端向中间走。维护 leftMax（left 指针见过的最大高度）和 rightMax（right 指针见过的最大高度）。

关键问题：当 left 指向某个位置 i 时，leftMax 是已知的（i 左边的最大值），但 rightMax（i 右边的真正最大值）还不完全知道。我们只知道从 right 到 n-1 这段的最大值，right 左边（i 右边的一部分）还没扫到。

双指针的精妙之处： 如果 leftMax < rightMax，那么位置 i 处的接水量是 leftMax - height[i]，而不需要知道真正的右边最大值！

为什么？因为此时 leftMax 是左边的真实最大值，rightMax 是右边目前见过的最大值（从 right 到 n-1）。由于 rightMax >= leftMax，而 right 左边（i 到 right 之间）必然有某个值也 >= rightMax，所以右边的真实最大值 >= rightMax >= leftMax。位置 i 处的水位 = min(左max, 右max) = leftMax，接水量 = leftMax - height[i]。

同理，如果 rightMax <= leftMax，处理 right 指针，接水量 = rightMax - height[right]。

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int total = 0;
        
        while (left < right) {
            // 更新左右最大值（注意：先更新再计算）
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            
            if (leftMax < rightMax) {
                // 左边更低，左边是木桶短板
                // 位置 left 处水位 = leftMax，接水量 = leftMax - height[left]
                total += leftMax - height[left];
                left++;
            } else {
                // 右边更低（或相等），右边是木桶短板
                total += rightMax - height[right];
                right--;
            }
        }
        
        return total;
    }
}

时间复杂度：O(n)，left 和 right 合计移动 n 次。

空间复杂度：O(1)，只用了常数个变量。

五、解法四：单调栈（横向计算积水）

核心洞见

前面三种解法都是纵向计算每个位置的积水（每列有多少水）。单调栈用横向计算：找到"凹槽"，一层一层地计算积水体积。

维护一个单调递减栈（栈中元素从栈底到栈顶高度递减）。当遇到一个高度比栈顶元素高的柱子时，说明找到了一个"右墙"，可以计算以栈顶为底部的这一层积水。

具体步骤：

  1. 遍历每个柱子 i。
  2. 当 height[i] > height[栈顶] 时，栈顶是凹槽底部，弹出栈顶。
  3. 此时新的栈顶是左墙，当前 i 是右墙。
  4. 积水宽度 = i - 新栈顶 - 1，积水高度 = min(height[左墙], height[右墙]) - height[底部]。
  5. 计算这一层的横向积水量，累加。

算法流程

完整 Java 代码

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>(); // 存下标
        int total = 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 leftWall = stack.peek();
                
                // 计算这一层的积水
                int width = i - leftWall - 1;
                int waterHeight = Math.min(height[leftWall], height[i]) - height[bottom];
                total += width * waterHeight;
            }
            
            stack.push(i); // 将当前位置入栈
        }
        
        return total;
    }
}

时间复杂度：O(n)，每个元素最多入栈出栈各一次。

空间复杂度：O(n)，栈的大小最坏情况是 n（单调递减序列）。

我在 LeetCode 提交双指针版本，运行时间 0ms，击败 100% 的 Java 用户。接雨水这道题算法优化的天花板就在 O(n) 时间、O(1) 空间，双指针完美达到。

六、举一反三

同类型题目

LeetCode 84. 柱状图中最大的矩形

下一篇的主题，单调栈的另一个经典应用。接雨水找凹槽，柱状图最大矩形找凸起，两者是"互反"的问题。

LeetCode 407. 接雨水 II（三维接雨水）

二维矩阵版本，需要用最小堆（优先队列）从边界向内找最低点，是这道题的三维扩展。

LeetCode 11. 盛最多水的容器

用两堵墙围成的最大面积。双指针解法，思路和接雨水双指针类似，但不需要考虑中间的柱子。

四种解法对比

解法时间空间适用场景难度
暴力O(n²)O(1)只是理解题意低
前缀数组O(n)O(n)标准解，代码最直观低
双指针O(n)O(1)面试最优解中
单调栈O(n)O(n)和柱状图最大矩形配合记忆高

面试中的变体和追问

  1. 双指针为什么是对的？感觉不直观。 答：关键在于"确定了短板就不需要知道另一边的精确最大值"。leftMax < rightMax 时，右边真实最大值必然 >= rightMax >= leftMax，所以短板确定是左边，可以直接计算。

  2. 单调栈为什么维护的是递减栈？ 答：维护递减栈是为了保证"底部 < 两侧墙壁"的凹槽结构。当遇到更高的柱子时，才可能形成新的积水区域。如果维护递增栈，就找不到有效的凹槽了。

七、踩坑实录

坑一：双指针中 leftMax/rightMax 更新顺序搞错

现象： 双指针版本计算结果偏小。

原因： 先计算积水再更新 max，导致用了过时的 max 值。

// 错误：先计算再更新
total += leftMax - height[left];  // leftMax 可能还没更新
leftMax = Math.max(leftMax, height[left]);
left++;

// 正确：先更新再计算
leftMax = Math.max(leftMax, height[left]);
total += leftMax - height[left];  // 这里 leftMax - height[left] >= 0，因为 leftMax >= height[left]
left++;

坑二：单调栈中弹出后忘记判断栈是否为空

现象： NullPointerException 或者数组越界。

原因： 弹出凹槽底部后，如果栈已经空了，说明没有左墙，不能积水，必须 break 而不是继续计算 stack.peek()。

坑三：前缀数组版本中 leftMax[i] 包不包含自身

现象： 计算结果出现负数，或者某些位置接水量多算了。

原因： 如果 leftMax[i] 定义为严格左边（不含 i 自身）的最大值，那么当 i 是局部最高点时，leftMax[i] < height[i]，接水量 = min(leftMax[i], rightMax[i]) - height[i] 可能是负数，需要加 Math.max(0, ...) 兜底。但如果 leftMax[i] 包含 i 自身，则 leftMax[i] >= height[i]，接水量非负，不需要特判。两种定义都对，但代码写法不同，要保持一致。

八、总结

接雨水这道题的四种解法，代表了算法思维的四个维度：暴力直觉、前缀数组、双指针降维、单调栈数据结构。每种解法都值得仔细理解。

三条核心要点：

  1. 接雨水的核心数学洞察：每个位置能接的水 = min(左边最高, 右边最高) - 当前高度。这个洞察是所有优化解法的基础。

  2. 双指针 O(1) 空间的关键：当左右最大值中较小的那个确定时，该侧的接水量就可以算了，不需要精确知道另一侧的最大值。

  3. 单调栈是"横向"逐层计算积水，和前面"纵向"按列计算的思路完全不同，两种思维都要掌握。

延伸思考：

这道题的双指针和前缀数组解法，体现了一个通用优化模式：当"左边状态"和"右边状态"可以分别维护时，用两个指针分别维护，就能把空间从 O(n) 降到 O(1)。这个思路在很多其他题目里也能用到，比如 LeetCode 238（除自身以外数组的乘积）。

编辑此页
最近更新:
贡献者: xiaozhangge