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

接雨水问题详解

给定 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)，完全满足题目性能要求。