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

1. 问题背景与核心挑战

LeetCode 42题"接雨水"是算法面试中的经典题目，也是动态规划和双指针技巧的典型应用场景。题目给定n个非负整数表示的高度图，每个柱子的宽度为1，计算下雨后这个高度图能接多少雨水。

我第一次遇到这个问题是在准备某大厂面试时，当时被这个看似简单实则暗藏玄机的问题难住了整整一个下午。后来经过反复推敲和多种解法对比，才真正理解了其中的精妙之处。这道题之所以能长期占据Hot 100榜单，是因为它完美考察了以下几个核心能力：

1. 对问题模型的抽象能力（如何将雨水体积转化为可计算的数学模型）
2. 对边界条件的处理能力（左右边界、空数组等特殊情况）
3. 对时间/空间复杂度的优化意识（从暴力解法到最优解法的演进）
4. 对多种解法的比较选择能力（不同场景下的适用性分析）

2. 问题分析与暴力解法

2.1 问题建模

首先我们需要明确雨水是如何被"接住"的。观察示例图可以发现，雨水会被两个较高的柱子"夹住"，形成凹槽。对于任意一个柱子i，它能接住的雨水量取决于：

1. 它左边最高的柱子高度left_max
2. 它右边最高的柱子高度right_max
3. 这两个高度中的较小值min(left_max, right_max)
4. 当前柱子的高度height[i]

因此，柱子i能接的雨水量为：min(left_max, right_max) - height[i]（如果结果为正）

2.2 暴力解法实现

最直观的思路是对每个柱子i，分别向左向右扫描找到最大高度：

cpp复制int trap(vector<int>& height) {
    int n = height.size();
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int left_max = 0, right_max = 0;
        // 向左找最大值
        for (int j = i; j >= 0; --j) {
            left_max = max(left_max, height[j]);
        }
        // 向右找最大值
        for (int j = i; j < n; ++