力扣 42. 接雨水：动态规划 / 单调栈 / 双指针 三种解法全解析（Java 实现）

一、引言

LeetCode 42 接雨水（Trapping Rain Water）是数组类算法题的经典代表，也是面试中的高频考点，这道题的核心是理解 “每个位置接雨水量由左右最大高度决定”，而动态规划、单调栈、双指针则是解决该问题的三大核心思路 —— 三者从不同角度切入，在时间 / 空间复杂度上各有优劣，也对应了不同的算法思想。

本文会系统拆解这三种解法：先通过动态规划理清核心逻辑（易理解但需额外空间），讲解双指针的最优解（O (n) 时间 + O (1) 空间），再用单调栈实现 “一次遍历 + 空间换时间” 的优化，并全部给出可直接运行的 Java 代码，帮助你从原理到实现彻底掌握这道题。

二、动态规划

2.1 解题步骤

朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。

我们可以清晰地看出可以接水的格子是左边最高和右边最高都是高于自己本身的高度，也就是凹下去，才能成功接水。而接水的高度则是左边右边最高中较矮的一侧减去自己本身

所以我们的解题步骤是：

• 先计算出当前柱子左边最高的柱子和右边最高的柱子
• 当前柱子接水面积 = （min(左高 ， 右高) - 自身高度）*1
• 将面积累加。

2.2 动态规划的使用

但是我们每次计算柱子的左高和右高都去遍历一次数组其实时间复杂度会达到O (n²)，所以我们可以使用动态规划。

动态规划（Dynamic Programming，简称 DP）核心是把复杂问题拆解成多个可重复解决的子问题，并把子问题的答案保存下来（避免重复计算），最终通过子问题的解推导出原问题的解。

• 我们把计算接水总面积拆分成计算单个柱子的接水面积
• 并且记录下单个柱子的左高和右高，方便计算下一个柱子的左高和右高
• 最后再把单个柱子的面子累加

2.3 代码实现

 /** * 动态规划 * @param height 柱子的高度 * @return 接住雨水的总数 */ public int trap(int[] height) { int len = height.length; // 当柱子个数小于三时，无法接到雨水 // 接雨水的条件是两边的比中间高，所以至少要有三个柱子 if (len < 3) { return 0; } //记录第i根柱子左边（包括自身）中最高柱子的高度 int[] leftMax = new int[len]; leftMax[0] = height[0]; for (int i = 1; i < len; ++i) { //复用上一根柱子的左高，优化了时间复杂度 leftMax[i] = Math.max(leftMax[i - 1], height[i]); } //记录第i根柱子右边（包括自身）中最高柱子的高度 int[] rightMax = new int[len]; rightMax[len - 1] = height[len - 1]; for (int i = len - 2; i >= 0; --i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } //把计算接水总面积拆分成计算单个柱子的接水面积 int ans = 0; for (int i = 0; i < len; ++i) { //当前柱子接水面积 = （min(左高 ， 右高) - 自身高度）*1 ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; }

三、双指针

3.1 空间复杂度的优化

动态规划的做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。

注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。动态规划里面我们采用先统一计算左高右高，再计算面积。那我们可不可以做到在计算左高右高的同时计算面积，这样计算过面积的柱子的左高右高就可以被释放，不用存储在数组里面，我们采用指针来代替。

3.2 问题的解决

但是现在问题来了，我们的leftMax是从左往右计算的，而rightMax是从右往左计算的，假设我们要从左边开始处理柱子的接水面积，那么我们不用担心leftMax，因为leftMax的计算方向和我们处理柱子的方向一致，可是rightMax我们就要遍历一整个数组来得出，并且我们向右移动柱子时又要重新计算rightMax，时间复杂度反而会提高，这该怎么办?

• 我们再来回顾一下计算接水面积的公式当前柱子接水面积 = （min(左高 ， 右高) - 自身高度）*1
• 如果我们在从左往右处理时能够确定左高=min(左高 ， 右高),那么我们就不需要去遍历一次数组得出右高了。

• 我们可以明确确定的是左指针的leftMax，和右指针的rightMax，因为指针移动方向和计算高度最值方向一致
• 当左指针的leftMax<右指针的rightMax , 左指针的leftMax=min(左指针的leftMax ， 左指针的rightMax)，因为右指针的rightMax<=左指针的rightMax
• 当左指针的leftMax>=右指针的rightMax , 右指针的rightMax=min(右指针的leftMax ， 右指针的rightMax)，因为右指针的leftMax>=左指针的leftMax

3.3 代码的实现

 /** * 双指针 * @param height 柱子的高度 * @return 接住雨水的总数 */ public int trap(int[] height) { int len = height.length; // 当柱子个数小于三时，无法接到雨水 // 接雨水的条件是两边的比中间高，所以至少要有三个柱子 if (len < 3) { return 0; } //定义左右指针 int left = 0, right = height.length - 1; /** * leftMax是左指针指向柱子左边（包括自身）中最高柱子的高度 * rightMax是右指针指向柱子右边（包括自身）中最高柱子的高度 * 我们可以明确确定的是左指针的leftMax，和右指针的rightMax * 因为指针移动方向和计算高度最值方向一致 */ int leftMax = 0, rightMax = 0; //把计算接水总面积拆分成计算单个柱子的接水面积 int ans = 0; while (left < right) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); //当前柱子接水面积 = （min(左高 ， 右高) - 自身高度）*1 if (leftMax < rightMax) { //左指针的leftMax=min(左指针的leftMax ， 左指针的rightMax) //因为右指针的rightMax<=左指针的rightMax ans += leftMax - height[left]; ++left; } else { //右指针的rightMax=min(右指针的leftMax ， 右指针的rightMax) //因为右指针的leftMax>=左指针的leftMax ans += rightMax - height[right]; --right; } } return ans; }

3.4 指针的停止

我们从代码中可知，leftMax < rightMax 移动左指针，leftMax >= rightMax移动右指针，最终会有一个指针到达最高处后停止不动，等待另外一个指针过来，直到left == right ，那么当left == right时已经退出了循环，此时指向的柱子的面积还没有计算，但是没有关系，因为在最高柱子上height[left] = height[right] = leftMax = rightMax， 算出来的面积也是0，所以算不算加不加都无所谓，就算把循环条件换成left <= right也没有事，只是不需要多此一举。

3.5 移动指针的条件

在官方给出的题解中，移动指针的条件是height[left] < height[right]，并给出了如果 height[left]<height[right]，则必有 leftMax<rightMax的结论，我们来证明一下

前提条件：

• height[left]<=leftMax
• height[right]<=rightMax

反证：

• 假设height[left] = 165 , leftMax = 180 , height[right] = 170 , rightMax= 170
• 显然这种情况是不可能存在的，因为180指向的值肯定在left左侧，如果height[right]小于等于180，会一直移动找到一个大于180的地方停下，所以停下的时候leftMax<rightMax

就也说我们刚开始都是左指针指向了leftMax，右指针指向rightMax,然后小的一方开始移动，大的一方保持当前的最值，小的一方会一直移动直到超过大的一方，停在当前最值，换另一方移动。

总的来说，刚开始两方都保持height[left]==leftMax，height[right]==rightMax

• 如果是height[left] < height[right]，也就是leftMax<rightMax，然后开始移动左指针，移动后有两种可能：
  • height[left] < height[right] ， 此时leftMax要么保持原样，leftMax<rightMax，要么leftMax更新，leftMax = height[left] < height[right]=rightMax，leftMax<rightMax
  • height[left] >= height[right]，此时leftMax = height[left] >= height[right]=rightMax ,leftMax>=rightMax
• 如果是height[left] >= height[right]，也就是leftMax>=rightMax，然后开始移动右指针，移动后有两种可能：
  • height[left] >= height[right] ， 此时rightMax要么保持原样，leftMax>=rightMax，要么leftMax更新，leftMax = height[left] >= height[right]=rightMax，leftMax>=rightMax
  • height[left] < height[right]，此时leftMax = height[left] < height[right]=rightMax, leftMax<rightMax

所以如果 height[left]<height[right]，则必有 leftMax<rightMax，如果 height[left] >=height[right]，则必有 leftMax>=rightMax

 /** * 双指针 * @param height 柱子的高度 * @return 接住雨水的总数 */ public int trap(int[] height) { int len = height.length; // 当柱子个数小于三时，无法接到雨水 // 接雨水的条件是两边的比中间高，所以至少要有三个柱子 if (len < 3) { return 0; } //定义左右指针 int left = 0, right = height.length - 1; /** * leftMax是左指针指向柱子左边（包括自身）中最高柱子的高度 * rightMax是右指针指向柱子右边（包括自身）中最高柱子的高度 * 我们可以明确确定的是左指针的leftMax，和右指针的rightMax * 因为指针移动方向和计算高度最值方向一致 */ int leftMax = 0, rightMax = 0; //把计算接水总面积拆分成计算单个柱子的接水面积 int ans = 0; while (left < right) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); //当前柱子接水面积 = （min(左高 ， 右高) - 自身高度）*1 //现在要么是height[left] == leftMax，要么是height[right] == rightMax if (height[left] < height[right]) { /** * 进入此处有三种情况: * 1.height[left] == leftMax and height[right] == rightMax * height[left] < height[right] => leftMax< rightMax * 2.height[right] == rightMax 并且 leftMax< rightMax 移动左指针后 * height[left] < height[right] ，此时leftMax要么保持原样 => leftMax< rightMax * 要么leftMax更新，leftMax = height[left] < height[right] = rightMax => leftMax< rightMax * 3.height[left] == leftMax 并且 leftMax>=rightMax 移动右指针后 * height[left] < height[right]，此时leftMax = height[left] < height[right]=rightMax => leftMax< rightMax */ //左指针的leftMax=min(左指针的leftMax ， 左指针的rightMax) //因为右指针的rightMax<=左指针的rightMax ans += leftMax - height[left]; ++left; } else { /** * 进入此处有三种情况: * 1.height[left] == leftMax and height[right] == rightMax * height[left] >= height[right] => leftMax>= rightMax * 2.height[right] == rightMax 并且 leftMax< rightMax 移动左指针后 * height[left] >= height[right]，此时leftMax = height[left] >= height[right]=rightMax => leftMax>= rightMax * 3.height[left] == leftMax 并且 leftMax>=rightMax 移动右指针后 * height[left] >= height[right] ，此时rightMax要么保持原样 => leftMax>= rightMax * 要么rightMax更新，leftMax = height[left] >= height[right] = rightMax => leftMax>= rightMax */ //右指针的rightMax=min(右指针的leftMax ， 右指针的rightMax) //因为右指针的leftMax>=左指针的leftMax ans += rightMax - height[right]; --right; } } return ans; }

四、单调栈

4.1 面积计算

我们上面两种解法都是当前柱子接水面积 = （min(左高 ， 右高) - 自身高度）*1，是纵向的，那么现在我们来思考一下横向该怎么计算？

凹槽接水面积 =（ min（左边界高度 ， 右边界高度）- 底部高度）* 底部宽度

4.2 栈的思想

如果我们要依次计算的话，从左边开始，记录1号的左边界 -> 1号的右边界 ->1号处理完毕-> 2号的左边界-> 3号的左边界-> 3号的右边界 - >3号处理完毕->2 号的右边界->2号处理完毕- >4号的左边界-> 4号的右边界->4号处理完毕

我们可以清晰看到3号比2号先处理完毕，后进先出，这是栈的思想。

4.3 入栈和出栈

首先入栈的都是作为凹槽的底部，每个元素都有可能会作为底部，所以每个元素都要入栈。

当当前元素值大于栈顶，那么就取出栈顶的元素作为凹槽的底部，当前元素作为凹槽的右边界，左边界则是取出元素后栈的顶部元素，左边界一定是比底部高的，因为如果左边界比底部低会被取出来形成一个凹槽，计算完当前凹槽面积后，若栈为空，或当前元素小于栈顶元素，右边界入栈，若仍然大于栈顶元素则继续计算凹槽

4.4 代码实现

 /** * 单调栈 * @param height 柱子的高度 * @return 接住雨水的总数 */ public int trap(int[] height) { int ans = 0; //栈中存放凹槽的底部 Deque<Integer> stack = new LinkedList<>(); int n = height.length; for (int i = 0; i < n; ++i) { //当栈中有元素，并且栈顶元素小于当前元素，可以作为凹槽的底部 while (!stack.isEmpty() && height[i] > height[stack.peek()]) { //取出栈顶元素作为凹槽底部 int top = stack.pop(); //如果栈中没有元素，那么就没有元素可以作为凹槽的左边界，无法成功接雨水，退出循环 if (stack.isEmpty()) { break; } //获取栈顶元素作为栈的左边界，左边界是一定大于底部的 //因为如果底部大于左边界，那么就会形成一个凹槽，在处理当前元素之前已经处理过了 //所以栈里面的元素肯定是越靠近栈底元素越大，这也就是单调栈 int left = stack.peek(); //计算凹槽底部 int currWidth = i - left - 1; //计算凹槽高度 int currHeight = Math.min(height[left], height[i]) - height[top]; //凹槽接水面积 =（ min（左边界高度 ， 右边界高度）- 底部高度）* 底部宽度 ans += currWidth * currHeight; } //当前元素作为右边界计算凹槽的面积已经计算完毕 //当前元素作为底部压入栈中 stack.push(i); } return ans; }

五、总结