42. 接雨水#

题目链接: LeetCode 42

题目描述#

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

示例 1：

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

示例 2：

1
输入：height = [4,2,0,3,2,5]
2
输出：9

解题思路#

核心思想#

每个位置能接的水量 = min(左侧最高柱, 右侧最高柱) - height[i]（若为正才接水）。用双指针：left、right 从两端向中间靠拢。关键在于：当 height[left] < height[right] 时，位置 left 的水量由左侧最高决定（此时右边界已经足够高），因此我们可以放心处理左指针。

算法步骤#

left=0, right=n-1, left_max=right_max=0, ans=0。
更新 left_max = max(left_max, height[left])、right_max = max(right_max, height[right])。
若 height[left] < height[right]：说明 left 处左边界是短板，ans += left_max - height[left]，left += 1。
否则：处理右侧，ans += right_max - height[right]，right -= 1。
重复直到 left >= right，返回 ans。

逐步举例#

height = [0,1,0,2,1,0,1,3,2,1,2,1]：

步骤	left	right	处理边	left_max	right_max	增量	ans
1	0	11	左(0<1)	0	1	0	0
2	1	11	左(1<1)→右	1	1	0	1
3	1	10	左(1<2)	1	2	1-1=0	1
4	2	10	左(0<2)	1	2	1-0=1	2
…	…	…	…	…	…	…	6

最终 ans = 6。

复杂度分析#

时间复杂度：O(n)，双指针各扫描一次。
空间复杂度：O(1)。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def trap(self, height: List[int]) -> int:
6
        left, right = 0, len(height) - 1
7
        left_max = right_max = 0
8
        ans = 0
9
        while left < right:
10
            left_max = max(left_max, height[left])
11
            right_max = max(right_max, height[right])
12
            if height[left] < height[right]:
13
                ans += left_max - height[left]
14
                left += 1
15
            else:
16
                ans += right_max - height[right]
17
                right -= 1
18
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_basic(self):
12
        self.assertEqual(Solution().trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]), 6)
13

14
    def test_flat(self):
15
        self.assertEqual(Solution().trap([0, 0, 0, 0]), 0)
16

17
    def test_high_middle(self):
18
        self.assertEqual(Solution().trap([4, 2, 0, 3, 2, 5]), 9)
19

20

21
if __name__ == '__main__':
22
    unittest.main()