圈圈工程師

Change Change Developer

0%

Leetcode 筆記 - 圖解解題 Trapping Rain Water (Hard)

發表於 分類於
圖解步驟解釋如何用雙指針的方法解題 Trapping Rain Water (Hard) 🙂

題目

Leetcode 題目網址 🚐

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.

翻譯年糕
給予一組正整數代表高度的地圖，
其中每一個寬度都是 1，
計算在下雨過後會有多少積水

範例

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.


解題關鍵 1

水位高度只會到最小的高度，
超過最小高度就會從另外一邊溢出，
因此取得左邊與右邊的最小高度，
即 min(leftHeight, rightHeight)


「左邊的最大高度」與「右邊的最大高度」

上述的左邊與右邊的最小高度的「左邊」與「右邊」，
必須是那「左邊的最大高度」與「右邊的最大高度」來做比較


🤯：「為什麼呢？」

例如以 i = 3 的這個情況來看：

左側最大的高度是 1，
右側最大的高度是 3，
i = 3 本身的高度（2）已經超過了 1 (min(leftHeight, rightHeight))，
因此不會有積水產生。


🤯：「為什麼 i = 3 的時候，
左側的最高高度是 1 ，
而不是 i = 3 的高度 2 呢？」

🙂：「因爲當 i 走到 3 的時候，
會先做完是否有積水的判斷，
然後在做 max(leftHeight, height[i]) 的動作。」


我們在以 i = 4 的情況來看：

左側最大的高度是 2，
右側最大的高度是 3，
i = 4 本身的高度（1）比 2 (min(leftHeight, rightHeight)) 還小，
因此會產生 1 個單位的積水量。


因此我們知道了必須是「左邊的最大高度」與「右邊的最大高度」來做比較。


計算積水量的方法

於是我們就可以推出計算積水量的方法：

min(leftMaxHeight, rightMaxHeight) - height[i]

🙂：「帶著這個理解，我們可以準備來解題囉。」


如何找到每一個 i 的 min(leftMaxHeight, rightMaxHeight) 的值？

🤯：「不過現在有個小問題，我們要怎麼知道每一個 i 的 min(leftMaxHeight, rightMaxHeight) 的值是什麼呢？ 」

我們可以先由左到右先找出每個 i 的左側最大高度：（動態圖裡更換最大高度時用箭頭表示）

再由右到左找出每個 i 在右側的最大高度：（動態圖裡更換最大高度時用箭頭表示）

之後在針對左側與右側的最大高度找出最小值即可 🎉

上述的操作就可以讓我們找到每一個 i 的 min(leftMaxHeight, rightMaxHeight) 放在 minHeights。

接下來我們只需要一次 for 迴圈，把 minHeights[i] - height[i] 的結果累加起來就可以囉！

如果 minHeights[i] - height[i] 爲負值，則用 0 取代，畢竟積水不會爲負的。

程式碼

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
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        maxLeftHeights = [0] * len(height)
        maxLeft = 0 
        # 由左往右找出左側的最大高度
        for i in range(len(height)):
            maxLeftHeights[i] = maxLeft
            maxLeft = max(height[i], maxLeft)				
				
        maxRightHeights = [0] * len(height)
        maxRight = 0
        # 由右往左找出右側的最大高度
        for i in range(len(height) - 1, -1, -1):
            maxRightHeights[i] = maxRight
            maxRight = max(height[i], maxRight)				

        mins = []
        # 找出 min(leftHeight, rightHeight)
        for i, maxLeft in enumerate(maxLeftHeights):
            mins.append(min(maxLeft, maxRightHeights[i]))

        res = 0
        for i, h in enumerate(height):
            res += max(0, mins[i] - h) # 如果結果爲負值，用 0 取代
									
        return res

快速看一下上述的解法的複雜度：

  • 時間複雜度： O(N)
    • 因爲只會跑 4 x N 次迴圈
  • 空間複雜度：O(N)
    • 因爲要用陣列儲存 leftHeights、rightHeights、minHeights 等內容


😬：「還可以在更好嗎？」


🙂：「可以的。」


空間複雜度 O(1) 解法

除了上面的解法，我們還可以用雙指針的方式來優化這題的解法。

解題關鍵 2

我們可以設定左指標 L 指著第一個元素，右指標 R 指著最後一個元素，
新增「左側最大高度」與「右側最大高度」的變數。

以下用 L 代表左指標、 R 代表右指標

如果「左側的最大高度」小於「右側的最大高度」，
那 L 就可以往右走一步，
那我們就可以直接用「左側的最大高度」減去目前 L 所在的高度了。

反之「左側的最大高度」大於等於「右側的最大高度」，
那 R 就可以往左走一步，
那我們就可以直接用「右側的最大高度」減去目前 R 所在的高度了。



🤯：「聽起來很棒，但爲啥呀？ 」

🙂：「還記得我們剛剛提過的計算積水的算法嗎？」

min(leftMaxHeight, rightMaxHeight) - height[i]

如果「左側的最大高度」小於「右側的最大高度」的情況，
是不是就代表著 min(leftMaxHeight, rightMaxHeight) 會得到 leftMaxHeight 值了？
所以就抓起來減去目前 L 的高度了啦！

反之「左側的最大高度」大於等於「右側的最大高度」的情況，
在 min(leftMaxHeight, rightMaxHeight) 會得到 rightMaxHeight 值了？
所以就抓起來減去目前 R 的高度了啦！



🤯：「那為什麼 L 或 R 要先走一步之後，在執行 min(leftMaxHeight, rightMaxHeight) - height[i] ?」

🙂：「因爲周圍的最左邊或最右邊，只有可能沒有高度或有高度兩種可能，是不會有積水的！」



🤯：「那什麼時候會執行結束呢？ 」

🙂：「如果 L 不再小於 R 就結束執行囉。」


* * *

帶著這個理解之後，我們就可以開始寫程式囉！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        L, R = 0, len(height) - 1
        leftMax, rightMax = height[L], height[R]
        res = 0
        while L < R:
            if leftMax < rightMax:
                L += 1
                leftMax = max(leftMax, height[L])
                res += leftMax - height[L]
            else:
                R -= 1
                rightMax = max(rightMax, height[R])
                res += rightMax - height[R]
        return res

🤯：「咦？為什麼會有 max(leftMax, height[L]) 的情況呢？」

🙂：「這樣做一樣是爲了避免會產生負數的狀況，
所以如果最大的高度小於目前的高度，
那先把目前的高度取代最大高度，
就可以在後來的相減得到 0 的結果囉。」

最後來看一下圖解上述步驟的過程囉：

最後看一下上述的解法的複雜度：

  • 時間複雜度： O(N)
  • 空間複雜度：O(1)

結論

這題真的滿多概念需要掌握才能理解解法 😬，
不愧是 Hard 的題目！
希望用圖解過程可以幫助路過的你，
也感謝你的收看！🎉

參考