題目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1

trapping-rain-water

1
2
3
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2

1
2
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

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

解釋題目

題目會給一個陣列，陣列值代表牆的高度，題目假設牆的寬度都是 1。牆跟牆之間可以儲水，最後要計算所有牆面可以儲多少水。

思路 (1) 雙指針

  1. 陣列是由一道一道牆所建立的，想像灌滿水，不讓水流出的關鍵是左右兩側的牆
  2. 左右兩側的牆分別代表兩個指針，並且會相向移動。
  3. 矮牆的那一端，就可以先計算水量，因為水會從矮的那一側流出。
    • 透過雙指針的相向移動，可以逐步比較兩側牆的高度。
    • 所以透過比較每次左右兩道牆，可以確保水一定不會外流。
    • 因為前面這個前提，所以可以逐步計算矮邊的水量。
  4. 若左牆較矮，當下的牆 (左牆) 可以跟 left_max ( 左高牆 ) 比較，相差值即為可以裝的水量。
    • 即便左右之間的牆都矮於左牆 => 水也不會流出
    • 即邊中間有高於右邊的牆 => 水也不會流出
  5. left_max 的初始值是左邊第一道牆，所以通常不能儲水是正常的。
  6. 左邊計算完水量，指針要往右移一步。
  7. 右邊是一樣的邏輯。

思路 (2) DP

  1. DP 的想法比較簡單，就是暴力地去計算每道矮牆的左右兩側牆高的陣列，left_max 跟 right_max。
  2. 然後因為知道每道牆的左邊最高 ( left_max[i] ) 跟右邊最高 ( right_max[i] )，就可以計算水量
  3. 當前牆高的水量的計算就是 left_max[i] 跟 right_max[i] 取小值，減去當前牆高 ( height[i] )，如果當前牆超級高，就不能存水，水為 0 不能為負。
  4. left_max 初始值為 height[0]；right_max 初始值為 height[n - 1]

程式碼 (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
class Solution:
    def trap(self, height: List[int]) -> int:
        # 雙指針
        left, right = 0, len(height) - 1

        # 初始的的高牆
        # 遍歷每一道牆，計算水量
        left_max, right_max = height[left], height[right]

        # 初始水量
        water = 0

        while left < right:
          # 左邊牆比較矮，代表左邊可以先處理
          # 因為左邊較矮，水只有可能從左邊流出去，想像水是由兩邊的牆包圍的
          # 不用在意中間的牆是否高高低低
          if height[left] < height[right]:

            # 水量取決於矮牆的高度
            # 當下這道牆是否可以存水，取決於是否比 left_max 矮
            # 即便 left_max 有可能高於 height[right]，但這不影響水最終會不會外流
            if height[left] < left_max:
              water += left_max - height[left]

            # 目前這道牆比較高，要取代目前的 left_max
            else:
              left_max = height[left]

            left += 1
          # 右牆較矮，代表可以處理右邊
          else:
            if height[right] < right_max:
              water += right_max - height[right]
            else:
              right_max = height[right]

            right -= 1

        return water

程式碼 (2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height) 
        left_max = [0] * n  
        right_max = [0] * n
      
        # 計算每道牆的 left_max
        left_max[0] = height[0]
        for i in range(1, n):
          left_max[i] = max(left_max[i - 1], height[i])

        # 計算每道牆的 right_max
        right_max[n-1] = height[n-1]
        for i in range(n - 2, -1, -1):
          right_max[i] = max(right_max[i + 1], height[i])

        # 計算每道牆水量
        water = 0
        for i in range(n):
          water += max(min(left_max[i], right_max[i]) - height[i], 0)

        return water