算法题：接雨水问题详解与动态规划解法

接雨水问题详解

给定 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 个单位的雨水（蓝色部分表示雨水）。

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

提示

n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5

解题思路

核心方法：动态规划预处理左右最大高度 + 逐列计算接水量。通过提前预存每个位置左右两侧的最大柱子高度，将'找左右最大高度'的时间复杂度从 O(n) 降至 O(1)，整体时间复杂度优化至 O(n)，是接雨水问题的经典高效解法。

具体步骤：

1. 核心原理铺垫：每个位置 i 能接住的雨水量 = min(位置 i 左侧最大高度，位置 i 右侧最大高度) - 位置 i 自身高度（若结果为正，否则接水量为 0）。这是因为雨水的高度由左右两侧更矮的'挡板'决定，且只有当挡板高度高于当前柱子时，才能接住雨水。
2. 预处理左侧最大高度数组 maxLeft：
   • 初始化长度与 height 相同的数组 maxLeft，maxLeft[i] 表示位置 i 左侧（不包含 i）的最大柱子高度。
   • 从左到右遍历数组（起始下标 i=1，因为下标 0 左侧无柱子）：maxLeft[i] = Math.max(maxLeft[i-1], height[i-1])，即当前位置的左侧最大高度 = 前一位置的左侧最大高度 和 前一位置柱子高度 的较大值，通过递推完成所有位置的左侧最大高度计算。
3. 预处理右侧最大高度数组 maxRight：
   • 初始化长度与 height 相同的数组 maxRight，maxRight[i] 表示位置 i 右侧（不包含 i）的最大柱子高度。
   • 从右到左遍历数组（起始下标 i=height.length-2，因为最后一个位置右侧无柱子）：maxRight[i] = Math.max(maxRight[i+1], height[i+1])，即当前位置的右侧最大高度 = 后一位置的右侧最大高度 和 后一位置柱子高度 的较大值，通过递推完成所有位置的右侧最大高度计算。
4. 逐列计算总接水量：
   • 初始化总接水量 sum=0，遍历数组中除首尾外的所有位置 i（首尾位置无两侧挡板，无法接水）。
   • 对每个位置 i，计算左右最大高度的较小值 min = Math.min(maxLeft[i], maxRight[i])。
   • 若 min > height[i]，说明当前位置能接水，接水量为 min - height[i]，将其累加到 sum；若 min <= height[i]，则接水量为 0，无需处理。
5. 返回结果：遍历完成后，sum 即为所有位置能接住的雨水总量，返回该值。

核心优化逻辑说明

1. 时间复杂度优化：若不预处理左右最大高度，直接对每个位置遍历左右找最大值，时间复杂度为 O(n²)（每个位置找左右最大值各需 O(n)），无法适配 n=2×10⁴ 的规模；动态规划预处理仅需两次 O(n) 遍历，后续逐列计算为 O(n)，整体时间复杂度为 O(n)，完全满足题目性能要求。
2. 空间复杂度说明：该解法用两个长度为 n 的数组存储左右最大高度，空间复杂度为 O(n)，这是'时间换空间'的典型应用——通过额外的 O(n) 空间开销，换取时间复杂度从 O(n²) 到 O(n) 的质的提升。

Java 代码实现

public int trap(int[] height) {
    int sum = 0;
    int[] maxLeft = new int[height.length];
    int[] maxRight = new int[height.length];
    
    // 预处理左侧最大高度
    for (int i = 1; i < height.length - 1; i++) {
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]);
    }
    
    // 预处理右侧最大高度
    for (int i = height.length - 2; i >= 0; i--) {
        maxRight[i] = Math.max(maxRight[i + 1], height[i + 1]);
    }
    
    // 计算总接水量
    for (int i = 1; i < height.length - 1; i++) {
        int min = Math.min(maxLeft[i], maxRight[i]);
        if (min > height[i]) {
            sum = sum + (min - height[i]);
        }
    }
    return sum;
}

总结

1. 该解法的核心是动态规划预处理：通过递推的方式提前计算每个位置的左右最大高度，避免重复遍历，将时间复杂度优化至 O(n)；
2. 接雨水的核心公式是 min(左最大高度，右最大高度) - 当前高度（结果为正才有效），这是所有接雨水解法的底层逻辑；
3. 该解法空间复杂度为 O(n)，是时间与空间的平衡选择，若追求极致内存效率，可改用双指针法（无需额外数组），但核心计算逻辑不变。