LeetCode 筆記 - 42. Trapping Rain Water
題目在此 42. Trapping Rain Water
給定一個整數陣列,代表每個位置的高度,請計算這些高度可以接多少雨水。

解題思維
這題可以用經典的 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 | class Solution: |