[2025-09-22] Leetcode 42. 接雨水（未得最优解）

题目

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

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
 
提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105
  


我的代码（Python）

version 1

class Solution:
    def trap(self, height: List[int]) -> int:
        result = 0
        # forward
        i, j = 0, 1
        while i < len(height):
            while j < len(height) and height[j] < height[i]:
                j += 1
            print(f'i: {i}, j: {j}')
            if j < len(height):
                for k in range(i + 1, j):
                    result += (height[i] - height[k])
                    height[k] = height[i]
            i,j = j, j + 1
        # backward
        l, m = len(height) - 1, len(height) - 2
        while l >= 0:
            while m >= 0 and height[m] <= height[l]:
                m -= 1
            if m >= 0:
                for n in range(l - 1, m, -1):
                    result += (height[l] - height[n])
            l, m = m, m - 1
        return result

version 2

class Solution:
    def trap(self, height: List[int]) -> int:
        result = 0
        leftMax = [0 for i in range(len(height))]
        rightMax = [0 for i in range(len(height))]
        # forward
        leftMax[0] = height[0]
        for i in range(1, len(height)):
            leftMax[i] = max(leftMax[i - 1], height[i])
        # backward
        rightMax[- 1] = height[-1]
        for i in range(len(height) - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])
        # calculate
        for i in range(len(height)):
            result += (min(leftMax[i], rightMax[i]) - height[i])
        return result

点评

做过题目，所以version 1很容易实现了，不过这是最简单直接的办法，时间效率不高 （虽然已经是O(n)）。
参考官方答案实现了version 2，不过与官方相比，优化空间更多。

• 创建数组的优化

        # leftMax = [0 for i in range(len(height))]
        # rightMax = [0 for i in range(len(height))]
        leftMax = [0] * n
        rightMax = [0] * n

• 长度参数化

    n = len(height)

这个在任何代码里都要考虑，不过往往会有编译器做优化。终究还是忽略了。

• result 计算

        # for i in range(n):
        #     result += (min(leftMax[i], rightMax[i]) - height[i])
        result = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))

这个也能节约非常多的时间。

结论：细节很重要！！！