如何修改Trapping Rain Water算法获取直方图各柱雨水高度（O(n)）

原接雨水问题以计算总储水量为目标，要改成输出每个柱体的雨水高度，核心逻辑是每个位置的雨水高度 = max(0, min(该位置左侧最大柱高, 该位置右侧最大柱高) - 当前柱高)。以下两种O(n)时间复杂度的实现方法：

方法一：左右前缀数组法 #

这种方法空间复杂度O(n)，逻辑直观易懂：

1. 构建left_max数组：left_max[i]表示第i个柱体左侧（不包含自身）的最大柱高。
   • 从左到右遍历数组，left_max[0] = 0（第一个柱左侧无元素），后续每个位置left_max[i] = max(left_max[i-1], height[i-1])
2. 构建right_max数组：right_max[i]表示第i个柱体右侧（不包含自身）的最大柱高。
   • 从右到左遍历数组，right_max[n-1] = 0（最后一个柱右侧无元素），后续每个位置right_max[i] = max(right_max[i+1], height[i+1])
3. 遍历每个位置计算雨水高度：
   • 对每个i，雨水高度 = max(0, min(left_max[i], right_max[i]) - height[i])，将结果存入输出数组。

示例验证 #

输入直方图：{0, 3, 0, 2, 0, 4, 0}

• 计算得到left_max = [0, 0, 3, 3, 3, 3, 4]
• 计算得到right_max = [4, 4, 4, 4, 4, 0, 0]
• 逐个位置计算：
  • i=0: min(0,4)-0=0 → 0
  • i=1: min(0,4)-3=0 → 0
  • i=2: min(3,4)-0=3 →3
  • i=3: min(3,4)-2=1 →1
  • i=4: min(3,4)-0=3 →3
  • i=5: min(3,0)-4 为负，取0 →0
  • i=6: min(4,0)-0=0 →0
    输出结果：{0, 0, 3, 1, 3, 0, 0}，符合要求。

方法二：双指针法（空间优化至O(1)） #

如果需要优化空间，可以用双指针法，仅用常数额外空间（输出数组除外）：

1. 初始化指针left=0，right = len(height)-1，left_max=0，right_max=0，输出数组res初始化为全0。
2. 循环遍历直到left > right：
   • 若height[left] <= height[right]：
     • 如果height[left] >= left_max，更新left_max = height[left]
     • 否则，res[left] = left_max - height[left]
     • left += 1
   • 否则：
     • 如果height[right] >= right_max，更新right_max = height[right]
     • 否则，res[right] = right_max - height[right]
     • right -= 1

这种方法通过双指针从两端向中间逼近，利用左右侧的最大高度差直接计算每个位置的雨水高度，时间复杂度O(n)，空间复杂度仅为输出数组的O(n)，额外空间O(1)。

内容的提问来源于stack exchange，提问作者user22785544