LeetCode接雨水问题：动态规划与双指针解法详解

1. 接雨水问题概述

LeetCode 42题"接雨水"是算法面试中的经典难题，考察对数组操作和空间优化的理解。题目给定n个非负整数表示柱子的高度图，计算这些柱子排列后能接多少雨水。这个问题在实际中有很多应用场景，比如建筑排水设计、地形蓄水计算等。

理解这个问题的关键在于"木桶效应"——一个木桶能装多少水取决于最短的那块木板。在本题中，每根柱子能接的雨水量取决于它左右两侧最高柱子中的较小值。具体来说：

• 对于第i根柱子，它能接的雨水量 = min(左侧最高柱子, 右侧最高柱子) - 当前柱子高度
• 如果结果为负数，说明当前柱子比两侧都高，无法接水，结果取0

2. 动态规划解法详解

2.1 基本思路

动态规划解法是最直观的方法，时间复杂度O(n)，空间复杂度O(n)。其核心思想是预先计算每个位置左右两侧的最高柱子高度，然后根据上述公式计算每个位置的积水量。

具体步骤：

1. 从左向右遍历，计算每个位置及其左侧的最高柱子高度(left_max)
2. 从右向左遍历，计算每个位置及其右侧的最高柱子高度(right_max)
3. 遍历每个位置，用min(left_max[i], right_max[i]) - height[i]计算该位置的积水量

2.2 代码实现与优化

cpp复制class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        
        vector<int> left_max(n);
        vector<int> right_max(n);
        
        // 计算左侧最大值
        left_max[0] = height[0];
        for (int i = 1; i < n; i++) {
            left_max[i] = max(left_max[i - 1], height[i]);
        }
        
        // 计算右侧最大值
        right_max[n - 1] = height