LeetCode 42接雨水问题 | 双指针法与动态规划详解引言接雨水Trapping Rain Water是 LeetCode 中一道极具挑战性的高频面试题编号为 42难度为 Hard。这道题的核心问题是在一个表示海拔高度的数组中计算能够接住多少雨水。想象一下二维平面上有一系列高度不同的柱子下雨后水会停留在柱子之间的凹陷处我们需要计算出总的蓄水量。这道题的解法多种多样包括双指针、动态规划和单调栈等体现了算法问题的多路径思考方式。接雨水问题之所以重要不仅因为它在面试中频繁出现更因为它展示了如何将一个看似简单的问题转化为复杂的算法设计。问题的关键在于理解每个位置能接多少雨水取决于其左边最高柱子和右边最高柱子中较矮的那一个。本文将深入剖析双指针法和动态规划两种主流解法帮助读者全面掌握这道经典问题。问题分析题目描述给定 n 个非负整数表示一个高度图其中每个柱子的宽度为 1计算下雨后能接多少雨水。如图所示黑色部分表示柱子蓝色部分表示可以接住的雨水。对于输入 [0,1,0,2,1,0,1,3,2,1,2,1]能接住的雨水总量为 6 个单位。直观理解理解接雨水的关键在于认识到每个位置能接的雨水量由其左右两侧的最高点共同决定。具体来说如果一个位置的高度为 h[i]其左边最高柱子的高度为 left_max右边最高柱子的高度为 right_max那么该位置能接的雨水量为 min(left_max, right_max) - h[i]当结果为正时。这个公式的物理意义是水在该位置能堆积到的高度由左右两侧较矮的那个最高点决定因为较矮的一侧会成为水流的瓶颈。如果较矮的一侧高度为 H那么水最多只能堆积到 H 的高度再高就会从那一侧流走。扣除当前位置柱子的高度就是该位置能蓄水的高度。问题难点接雨水问题的主要难点在于如何在 O(n) 时间复杂度内解决。暴力的两遍遍历方法需要预先计算每个位置左右两侧的最高值这需要 O(n) 的空间复杂度。更优的双指针法可以在 O(1) 空间复杂度内达到同样的效果体现了对问题的深入理解和巧妙转化。暴力解法分析基础思路最直接的解法是遍历每个位置计算该位置左右两侧的最高柱子然后应用上面的公式求能接的雨水量。这种方法需要两遍遍历第一遍从左到右计算每个位置的左侧最高值第二遍从右到左计算每个位置的右侧最高值。然后第三遍遍历计算每个位置的蓄水量。def trap_brute_force(heights): n len(heights) if n 3: return 0 water 0 for i in range(1, n - 1): left_max max(heights[:i 1]) right_max max(heights[i:]) water min(left_max, right_max) - heights[i] return water这种方法的时间复杂度为 O(n²)因为每次计算 left_max 和 right_max 都可能遍历整个数组。虽然代码简洁直观但在处理大规模数据时效率低下无法满足实际应用的需求。预处理优化为了避免重复计算我们可以预先计算每个位置的左右最大高度。第一遍从左到右遍历记录到每个位置为止的最大值第二遍从右到左遍历记录从每个位置到右端的最大值。这样预处理后计算每个位置的蓄水量只需要 O(1) 的时间。def trap_preprocessed(heights): n len(heights) if n 3: return 0 left_max [0] * n right_max [0] * n for i in range(n): left_max[i] heights[i] if i 0 else max(left_max[i - 1], heights[i]) for i in range(n - 1, -1, -1): right_max[i] heights[i] if i n - 1 else max(right_max[i 1], heights[i]) water 0 for i in range(1, n - 1): water min(left_max[i], right_max[i]) - heights[i] return water这种预处理方法的时间复杂度为 O(n)空间复杂度也为 O(n)。虽然效率已经很好但还有进一步优化空间复杂度的可能。双指针法详解核心思想双指针法的核心思想是利用接雨水问题的单调性特性。在预处理方法中对于位置 i我们需要知道 left_max[i] 和 right_max[i]然后取两者中的较小值 min(left_max[i], right_max[i]) 作为决定该位置蓄水量的关键值。关键观察是对于位置 ileft_max[i] 必然大于等于 left_max[i-1]因为是从左到右累积的right_max[i] 必然大于等于 right_max[i1]因为是从右到左累积的。在双指针法中我们维护两个指针 left 和 right分别指向数组的两端同时维护两个变量 left_max 和 right_max分别记录左右两侧的最大高度。关键洞察是当 left_max[i] right_max[i] 时该位置的蓄水量由 left_max[i] 决定反之当 left_max[i] right_max[i] 时该位置的蓄水量由 right_max[i] 决定。这个结论的证明基于一个重要事实无论我们选择哪一侧的较小最大值较短的一侧都不可能为我们提供更大的值。证明过程让我们更形式化地证明上述结论。考虑指针位于位置 i左侧和位置 j右侧时的情况假设 left_max[i] right_max[j]。对于位置 i其右边最高柱子至少是 right_max[j]因为 right_max[j] 是整个右侧的最大值因此位置 i 能接的雨水量为 min(left_max[i], right_max[i]) - heights[i] left_max[i] - heights[i]因为 left_max[i] right_max[i] right_max[t] 对于所有 t i。由于 left_max[i] 是位置 i 左侧的最大高度我们已经知道了这个值可以立即计算位置 i 的蓄水量。这就是为什么当 left_max[i] right_max[j] 时我们可以移动左指针而不是等待知道完整的 right_max[i]。这个证明展示了双指针法的正确性基础。完整代码实现def trap_two_pointers(heights): n len(heights) if n 3: return 0 water 0 left, right 0, n - 1 left_max, right_max heights[left], heights[right] while left right: if left_max right_max: left 1 left_max max(left_max, heights[left]) water left_max - heights[left] else: right - 1 right_max max(right_max, heights[right]) water right_max - heights[right] return water这段代码的精妙之处在于每次移动指针后立即可以计算出移动后位置的蓄水量因为此时我们已经有足够的信息即较矮一侧的最大高度。当 left_max right_max 时我们选择移动左指针因为 left_max 是较短的木板我们已经知道它的确切值可以立即处理左侧当前位置反之亦然。动态规划方法备忘录方法动态规划方法实际上是预处理优化的一种体现它利用了问题的最优子结构性质。对于每个位置 i能接的雨水量只取决于 left_max[i] 和 right_max[i]这两个值可以分别通过一次遍历预处理得到。动态规划的优势在于将问题分解为更小的子问题分别解决后再组合。def trap_dp(heights): n len(heights) if n 3: return 0 left_max [0] * n right_max [0] * n water 0 left_max[0] heights[0] for i in range(1, n): left_max[i] max(left_max[i - 1], heights[i]) right_max[n - 1] heights[n - 1] for i in range(n - 2, -1, -1): right_max[i] max(right_max[i 1], heights[i]) for i in range(1, n - 1): water min(left_max[i], right_max[i]) - heights[i] return water这个方法直观清晰易于理解和实现但需要 O(n) 的额外空间。当内存受限或数据规模极大时可能需要考虑使用双指针法来将空间复杂度降低到 O(1)。空间优化如果我们再仔细观察动态规划的过程会发现 left_max 数组和 right_max 数组在计算完每个位置的蓄水量后就不再需要了。双指针法正是利用了这一点通过维护两个变量来代替整个数组从而将空间复杂度从 O(n) 降低到 O(1)。这种空间优化在处理大规模数据时可能非常关键。单调栈方法核心思想单调栈是解决接雨水问题的第三种主流方法它与前两种方法有着本质的不同。双指针法和动态规划法都是基于计算每个位置左右最大值的思想而单调栈法则采用了不同的视角它从低到高或高到低处理高度通过栈来维护一个递减的高度序列。具体来说我们遍历数组的每个位置对于每个新的高度 h我们检查它与栈顶高度的关系。如果当前高度大于栈顶高度说明在栈顶位置可以形成凹陷可以接雨水如果当前高度等于栈顶高度我们将其作为相同的条形处理通常只保留一个。每次遇到一个更高的条形时我们就弹出栈顶计算凹陷处的蓄水量。代码实现def trap_monotonic_stack(heights): stack [] water 0 n len(heights) for i in range(n): while stack and heights[i] heights[stack[-1]]: top stack.pop() if not stack: break distance i - stack[-1] - 1 bounded_height min(heights[i], heights[stack[-1]]) - heights[top] water distance * bounded_height stack.append(i) return water单调栈方法的时间复杂度为 O(n)空间复杂度为 O(n)。虽然空间复杂度不如双指针法优秀但单调栈方法在某些特定场景下可能更有优势例如需要同时知道每个位置左右第一个更高柱子的索引时。算法对比时间复杂度对比三种方法的时间复杂度都是 O(n)但常数因子可能有所不同。双指针法只需要一次遍历虽然内部循环中指针会多次移动动态规划需要三次遍历单调栈也需要一次遍历。在实际运行中双指针法通常是最快的因为它只涉及指针移动和常数次比较操作。空间复杂度对比在空间复杂度方面双指针法最优只需要 O(1) 的额外空间动态规划法和单调栈法都需要 O(n) 的额外空间。对于内存受限的环境双指针法是最佳选择。适用场景对比不同的方法适用于不同的场景。双指针法适用于只需要计算总蓄水量的问题动态规划法虽然空间复杂度高但概念简单易于理解和实现单调栈法在需要知道详细蓄水位置或其他相关信息时可能更有优势。在实际面试中面试官可能会要求使用多种方法解决问题以考察面试者对不同算法的掌握程度。测试用例def test_trap_rain_water(): assert trap_two_pointers([0,1,0,2,1,0,1,3,2,1,2,1]) 6 assert trap_two_pointers([4,2,0,3,2,5]) 9 assert trap_two_pointers([1,0,1]) 1 assert trap_two_pointers([3,0,0,2,0,4]) 10 assert trap_two_pointers([]) 0 assert trap_two_pointers([1]) 0 assert trap_two_pointers([1,2]) 0 print(所有测试用例通过)总结接雨水问题是算法学习中的经典问题它展示了如何将一个直观的问题转化为巧妙的算法设计。通过双指针法、动态规划法和单调栈法三种不同的解法我们可以看到同一问题可以从多个角度理解和解决。双指针法以其 O(1) 的空间复杂度成为最优解法其核心思想是利用较矮一侧的最大值总是可以立即确定这一洞察。掌握接雨水问题不仅有助于面试成功更能提升对算法思想的理解深度。希望本文的详细讲解能够帮助读者彻底理解这一经典问题并在今后的编程实践中灵活运用这些算法技巧。