LeetCode 筆記 - 42. Trapping Rain Water

Posted on

題目在此 42. Trapping Rain Water

給定一個整數陣列，代表每個位置的高度，請計算這些高度可以接多少雨水。

rainwatertrap

解題思維

這題可以用經典的 Two Pointer 來解決，主要是利用兩個指標 left 和 right，分別從陣列的兩端開始往中間移動。

在移動的過程中，我們需要維護兩個變數 left_max 和 right_max，分別代表目前 left 和 right 指標所看到的最高高度。

當 height[left] < height[right] 時，表示左邊的高度較低，因此我們可以確定左邊的水位是由 left_max 決定的。
如果 height[left] 小於 left_max，則表示在這個位置可以接到水，水量為 left_max - height[left]。然後將 left 指標往右移動。

反之亦然，當 height[left] >= height[right] 時，表示右邊的高度較低，因此我們可以確定右邊的水位是由 right_max 決定的。
如果 height[right] 小於 right_max，則表示在這個位置可以接到水，水量為 right_max - height[right]。然後將 right 指標往左移動。

Time Complexity 為 $O(n)$，Space Complexity 為 $O(1)$。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def trap(self, height: List[int]) -> int:

        # step 0: we use two pointer to solve this problem
        # step 1: if height[left] < height[right], which means the shorter side is the water height
        # use left_max to store 0 ~ height[left], the highest height
        # if left_max <= height[left], no water
        # else: current water height = left_max - height[left]
        # time complexity: O(n)
        # space complexity: O(1)

        if (size := len(height)) <= 2:
            return 0

        left = 0
        right = size - 1

        left_max = 0
        right_max = 0

        result = 0

        while left < right:

            if height[left] < height[right]:

                if left_max <= height[left]:
                    left_max = height[left]
                else:
                    result += left_max - height[left]

                left += 1
            
            else:
                # height[left] >= height[right]:

                if right_max <= height[right]:
                    right_max = height[right]
                else:
                    result += right_max - height[right]

                right -= 1

        return result

也許你也會想看看