接雨水

约 1644 字大约 5 分钟

2025-06-30

问题

42.接雨水

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

示例 1

**输入：**height = [0,1,0,2,1,0,1,3,2,1,2,1]
**输出：**6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

练习

接雨水

# your python code

思路

北海啊，要多想！

找到最高的柱子

在最终的积水状态下，水面必然呈现 " 山峰 " 形状——以最高柱子为顶点，左侧水位单调递增，右侧水位单调递减。

想象水被完全填满后的稳定状态：如果最高柱子左侧某处水位出现 " 凹陷 "（即某点水位比右邻居低），水会从右边流到左边，直到这个凹陷被填平。同理，右侧如果有 " 凹陷 "，水也会流动填平。因此，最终稳定时，必然是左侧递增、右侧递减的形状。

基于上述性质，算法可以分两个阶段：

找到最高的柱子所在位置。
依次遍历最高的柱子两侧：
- 左侧正向遍历：每个位置的积水量 = 水位 - 到目前为止遇到的最高柱子高度。
- 右侧反向遍历：每个位置的积水量 = 水位 - 到目前为止遇到的最高柱子高度。

Java


import java.util.Deque;  
import java.util.LinkedList;  
import java.util.Scanner;  
  
public class LC42Trap {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // int n = scanner.nextInt();
        // int[] height = new int[n];
        // for (int i = 0; i < n; i++) {
        //     height[i] = scanner.nextInt();
        // }
        
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};  
        // int[] height = {0,0,0};  
  
        System.out.println(trap(height)); 
    }  
  
    private static int trap(int[] height) {  
        /*  
        找到最高的柱子  
         */
         int S = 0, n = height.length;  
  
        // 1. 找到最高的柱子  
        int maxPos = -1, maxHeight = 0;  
        for (int i = 0; i < n; i++) {  
            if (height[i] > maxHeight) {  
                maxPos = i;  
                maxHeight = height[i];  
            }
        }  
        // 2. 依次遍历最高的柱子左侧和右侧  
        int waterHeight = height[0], i = 0;  
        while (i < maxPos) {  
            if (height[i] > waterHeight) {  
                waterHeight = height[i];  
            }
            S += waterHeight - height[i];  
            i++;  
        }
        waterHeight = height[n-1];  
        i = n - 1;  
        while (i > maxPos) {  
            if (height[i] > waterHeight) {  
                waterHeight = height[i];  
            }
            S += waterHeight - height[i];  
            i--;  
        }
        return S;  
    }

复杂度分析：

时间复杂度： $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(1)$ 。

动态规划

每个位置能接的雨水量取决于：

该位置左侧的最大高度。
该位置右侧的最大高度。
两者的最小值减去当前柱子高度。

因此，若定义

lefMax[i]：位置 i 左侧（包含 i）的最大柱子高度。
rightMax[i]：位置 i 右侧（包含 i）的最大柱子高度。

则每个柱子的接水量为 min(leftMax[i], rightMax[i]) - height[i]。

Java

import java.util.Deque;  
import java.util.LinkedList;  
import java.util.Scanner;  
  
public class LC42Trap {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // int n = scanner.nextInt();        
        // int[] height = new int[n];        
        // for (int i = 0; i < n; i++) {        
        //     height[i] = scanner.nextInt();        
        // }        
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};  
        // int[] height = {0,0,0};  
    
 
        System.out.println(trap_dp(height));
    }

	private static int trap_dp(int[] height) {  
	    /*  
	    动态规划  
	     */
	    int S = 0, n = height.length;  
	    int[] leftMax = new int[n], rightMax = new int[n];  
	    leftMax[0] = height[0];  
	    rightMax[n-1] = height[n-1];  
	  
	    // 1. 计算每根柱子左右侧的最大值  
	    for (int i = 1; i < n; i++) {  
	        leftMax[i] = Math.max(leftMax[i-1], height[i]);  
	        rightMax[n-i-1] = Math.max(rightMax[n-i], height[n-i-1]);  
	    }  
	    // 2. 计算每根柱子的接水量  
	    for (int i = 0; i < n; i++) {  
	        S += Math.min(leftMax[i], rightMax[i]) - height[i];  
	    }  
	    return S;  
	}
}

复杂度分析：

时间复杂度： $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(N)$ 。

双指针

使用两个指针 left right 分别从数组两端向中间移动，同时维护左右两侧的最大值 leftMax rightMax，根据左右最大值的大小关系来决定移动哪个指针。

如果 height[left] < height[right]：

说明左边“短板”更短，决定由左侧来承载水。
当前位置能积水 leftMax - height[left]。
更新 leftMax = max(leftMax, height[++left])；

否则（height[left] >= height[right]）：

说明右边短板更短，由右侧来承载水
当前位置能积水 rightMax - height[right]。
更新 rightMax = max(rightMax, height[++right])；

在上述的任一步骤中，总是先处理较低一侧，保证了该侧的 max 值不会被另一侧“假象”得高，从而正确计算当前柱子上方能积的水量。

Java

import java.util.Deque;  
import java.util.LinkedList;  
import java.util.Scanner;  
  
public class LC42Trap {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // int n = scanner.nextInt();        
        // int[] height = new int[n];        
        // for (int i = 0; i < n; i++) {        
        //     height[i] = scanner.nextInt();        
        // }        
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};  
        // int[] height = {0,0,0};  
    
 
        System.out.println(trap_dp(height));
    }

	private static int trap_point(int[] height) {  
	    /*  
	    双指针  
	     */
	    int S = 0, n = height.length;  
	    int left = 0, leftMax = height[left];  
	    int right = n-1, rightMax = height[right];  
	  
	    while (left < right) {  
	        if (height[left] < height[right]) {  
	            S += leftMax - height[left];  
	            leftMax = Math.max(leftMax, height[++left]);  
	        } else {  
	            S += rightMax - height[right];  
	            rightMax = Math.max(rightMax, height[--right]);  
	        }    
	    }  
	    return S;  
	}
}

复杂度分析：

时间复杂度： $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(1)$ 。

单调栈

使用单调递减栈来找到每个位置左右两边第一个比它高的柱子，从而计算能接住的雨水。

我们维护这样一个栈：栈中存储柱子的索引，并且保持栈从底到顶单调递减（即栈底元素对应的高度最大）。

对于每个位置 i：

当前高度 $\leq$ 栈顶高度：直接将索引 i 入栈。
当前高度 $>$ $>$ 栈顶高度：说明找到了一个右边界，可以接水。
- 当弹出栈顶元素时：弹出的索引 top 作为凹槽底部，左边界 left 为新的栈顶索引，右边界为当前索引 i 。
- 凹槽宽度：i - left - 1。
- 凹槽高度：min(height[i], height[left]) - height[top]。

Java

import java.util.Deque;  
import java.util.LinkedList;  
import java.util.Scanner;  
  
public class LC42Trap {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // int n = scanner.nextInt();        
        // int[] height = new int[n];        
        // for (int i = 0; i < n; i++) {        
        //     height[i] = scanner.nextInt();        
        // }        
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};  
        // int[] height = {0,0,0};  
    
 
        System.out.println(trap_dp(height));
    }

	private static int trap_stack(int[] height) {  
	    /*  
	    单调栈  
	     */    
	    int S = 0, n = height.length;  
	    Deque<Integer> stack = new LinkedList<>();  
	  
	    for (int i = 0; i < n; i++) {  
	        // 1. 比较 height[i] 与栈顶大小，维护单调栈  
	        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {  
	            int top = stack.pop();  
	            if (stack.isEmpty()) {  
	                break;  
	            }            
	            // 2. 计算当前洼面积  
	            int left = stack.peek();  
	            S += (i - left - 1) * (Math.min(height[i], height[left]) - height[top]);  
	        }        
	        stack.push(i);  
	    }    
	    return S;  
	}
}

复杂度分析：

时间复杂度： $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(N)$ 。

双指针

滑动窗口

子串

链表

图论

接雨水

问题

练习

接雨水

思路

找到最高的柱子

动态规划

双指针

单调栈