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

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]) 作为决定该位置蓄水量的关键值。关键观察是：对于位置 i，left_max[i] 必然大于等于 left_max[i-1]（因为是从左到右累积的），right_max[i] 必然大于等于 right_max[i+1]（因为是从右到左累积的）。

在双指针法中，我们维护两个指针 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) 的空间复杂度成为最优解法，其核心思想是利用较矮一侧的最大值总是可以立即确定这一洞察。

掌握接雨水问题不仅有助于面试成功，更能提升对算法思想的理解深度。希望本文的详细讲解能够帮助读者彻底理解这一经典问题，并在今后的编程实践中灵活运用这些算法技巧。