42. Trapping Rain Water

42. Trapping Rain Water

要寫這一題之前,要先了解 11. Container With Most Water 的概念,這一題比較特別,題目給定的陣列像是表達一個等高線圖,其中這個等高線內就會有山谷,有山谷的地方就能儲存水,我們要求出總共能夠有多少水被儲存在這個山谷。

先了解這個題目給的所有條件,那就是如果說今天給定的等高線圖,如果只有兩個點,這樣是沒有辦法儲存任何水的,山谷能有的最多水要被包在兩側的山峰內。如果只有一邊有高峰,那水都會流走。

也就是說最少要有類似 [1, 0, 1] 這樣的情況才能有水。

接著分析比較複雜一點的情況,像是 [1, 0, 2, 1, 3] 這樣的話,在位置 0 到 2 之間,其山谷是 [1, 0, 2] ,這和之前水桶的問題一樣,最多只能儲存一單位的水,下一個儲存水的地方是 [2, 1, 3] ,不過這裡最多只能儲存一單位的水。所以題目的答案就是 2 。

下一個例子,[1, 0, 2, 1, 1, 1, 1, 1, 3] 這樣的情況的話,第一個部分和上面一樣,但是右邊第二的部分就會有點不好算了,因為我們要不斷的找到右邊界,才能知道能裝多少水。

這個例子還算好處理的,如果上面的這個例子稍微修改一點點,[1, 0, 2, 1, 0, 1, 0, 1, 3] 這樣就不能單純的只找右邊的高點了,因為中間有更深的山谷,會可以儲存更多的水,又或是 [1, 0, 2, 1, 1, 1, 1, 1, 1] 這樣的例子,其實右邊只是一塊平地,根本不能裝水。

其實到這裡,我有想過該不會是要透過遞迴來處理?把大問題慢慢分解成小問題來處理?可是如果每次遞迴時,如果傳一個子陣列進去,子陣列會不知道上層問題的兩側高度,可能會造成在子問題中看起來儲存不了水,但是實際上可以的,這樣就會漏算面積,這個要怎麼判斷儲存水量的方法,就是這題最困難的地方。

但是回到一開始 [1, 0, 1] 的例子,如果說我們現在正在座標為 1 的時候,如果說我們知道哪些資訊,就可以確定那個位置可以裝水?這個比較好想,那就是在他的右手邊,一定有一個座標的高度比他高,在他的左手邊,也一定有一個座標的高度比他高。像是更複雜的例子,[1, 0, 2, 1, 1, 1, 1, 1, 3] 在座標 3 ~ 7 的山谷中,我們也都知道左邊有座標比他們都高,右邊也有座標比他們都高,因此這樣也就能確定那邊一定可以裝水。

有了這個想法後,可以再回到 [1, 0, 2, 1, 3] 的例子,座標 13 都可以裝水,雖然一個高度是 0 ,一個高度是 1 ,但是能裝的水容量都一樣是 1 ,因為他們那一個格子的容量,都被兩邊高度的最小值給決定了,而該格可以裝的容量就是 min(maxHeightFromLeft, maxHeightFromRight) - height[i] ,有了這個資訊後,只要去思考 maxHeightFromLeftmaxHeightFromRight 的意義就好,我們只記錄最大值這樣是合理的嗎?這時候可以看一個極端一點的例子 [1, 100, 0, 10, 5, 200] 在座標 4 的地方,高度是 5 ,右側的高度我們應該要看 10 還是 100 ?看 10 是不對的,因為 10 的左側其實是 100 他也能繼續裝到 100 的高度。

分析到這裡,就可以開始寫程式了,下一個難點是在於,為什麼一樣可以繼續用二分搜索的方式來做遍歷?其實這個和題目的特性有關,如果左側的邊界比較矮,代表左側邊界才是決定每個位置的山谷可以裝多少水的邊界,這時候就要從左邊往中間搜尋,看哪些地方比他矮並找出能裝多少水。

像是:[5, 4, 3, 2, 1, 100] 這時候右邊基本上是不用動的,我們要擔心的反而應該像是 [5, 4, 3, 2, 1, 100, 2, 3, 4, 5, 6] 這種,中間有一個很高的山峰,把兩側山谷分開的情況,這個情況反而很好解釋為什麼要用二分搜索的方式來找,當開啟上帝之眼來觀看的時候,從左側不斷的往中間前進是非常合理的事情,當走到山峰 100 的時後才會換右側往中間搜尋。

class Solution:
    def trap(self, height: List[int]) -> int:        
        if len(height) <= 2:
            return 0

        left = 0
        right = len(height) - 1
        area = 0

        while left < right:
            leftHeight = height[left]
            rightHeight = height[right]

            if leftHeight <= rightHeight:
                left += 1
            elif leftHeight > rightHeight:
                right -= 1
        return area

剩下一個我們需要的資訊,那就是當我從否一個方向往中間出發的時候,另一側的最大高度為何?所以我們需要有另外兩個變數來幫助我們更新位置 i 左右兩側的最大值。一開始的最大高度就是最兩側是因為最左和最右側的點,不管怎麼樣都一定無法儲存水份,就會把兩側端點設定為暫時的兩側最大值。

接著就可以看要從左側往中間前進,或是右側往中間前進,到了這裡只剩下最後個一個地方要處理,那就是也有可能,這座山就是 [1, 2, 3, 3, 2, 1] 根本沒有任何山谷,所以不管我們怎麼往中間走,都不會有任何的山谷可以存水,遇到這種情況,那就是要看當下的位置,是不是比目前記錄到的最大值還高,如果是的話,我們就更新該側的最大值就好,該格絕對沒有辦法儲存水。

class Solution:
    def trap(self, height: List[int]) -> int:        
        if len(height) <= 2:
            return 0

        left = 0
        right = len(height) - 1

        maxHeightFromLeft = height[0]
        maxHeightFromRight = height[len(height) - 1]

        area = 0

        while left < right:

            leftHeight = height[left]
            rightHeight = height[right]

            if leftHeight <= rightHeight:

                if leftHeight >= maxHeightFromLeft:
                    maxHeightFromLeft = leftHeight
                else:
                    area += maxHeightFromLeft - leftHeight
                left += 1

            elif leftHeight > rightHeight:

                if rightHeight >= maxHeightFromRight:
                    maxHeightFromRight = rightHeight
                else:
                    area += maxHeightFromRight - rightHeight
                right -= 1

        return area