接雨水问题

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

示例：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：可以接 6 个单位的雨水（蓝色部分表示雨水）。

解题思路
这个问题可以通过多种方法解决，我们从最直观的暴力法开始，逐步优化到最优解。

方法一：暴力法（按列计算）
核心思想：对于每个柱子，找出其左边和右边的最高柱子，然后计算该柱子能接的雨水量。

具体步骤：

1. 遍历数组中的每个元素（代表当前柱子）
2. 向左扫描，找到当前柱子左边最高的柱子高度 left_max
3. 向右扫描，找到当前柱子右边最高的柱子高度 right_max
4. 当前柱子能接的雨水量 = min(left_max, right_max) - 当前柱子高度
5. 如果结果为负数，则按 0 计算
6. 将所有柱子的接水量累加

时间复杂度：O(n²)，空间复杂度：O(1)

方法二：动态规划（预处理最大值）
优化思路：预先计算每个位置的左右最大值，避免重复扫描。

具体步骤：

1. 创建两个数组 left_max 和 right_max
2. left_max[i] 表示位置 i 左边的最高柱子高度（包括 i）
   • left_max[0] = height[0]
   • left_max[i] = max(left_max[i-1], height[i])
3. right_max[i] 表示位置 i 右边的最高柱子高度（包括 i）
   • right_max[n-1] = height[n-1]
   • right_max[i] = max(right_max[i+1], height[i])
4. 遍历每个位置，计算雨水量：min(left_max[i], right_max[i]) - height[i]

时间复杂度：O(n)，空间复杂度：O(n)

方法三：双指针法（最优解）
优化思路：在动态规划基础上优化空间复杂度，使用双指针从两端向中间遍历。

具体步骤：

1. 初始化 left = 0, right = n-1
2. 初始化 left_max = 0, right_max = 0（记录遍历过程中的左右最大值）
3. 当 left < right 时循环：
   • 如果 height[left] < height[right]：
     • 如果 height[left] ≥ left_max，更新 left_max
     • 否则，累加雨水量：left_max - height[left]
     • left++
   • 否则：
     • 如果 height[right] ≥ right_max，更新 right_max
     • 否则，累加雨水量：right_max - height[right]
     • right--

关键理解：我们总是移动高度较小那边的指针，因为接水量由较矮的那边决定。

时间复杂度：O(n)，空间复杂度：O(1)

代码实现（双指针法）

def trap(height):
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    result = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                result += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                result += right_max - height[right]
            right -= 1
    
    return result

总结
接雨水问题考察对数组操作和双指针技巧的掌握。从暴力法到动态规划再到双指针法的优化过程，体现了算法设计中常见的优化思路：通过预处理减少重复计算，再通过空间优化降低空间复杂度。