[LeetCode解題攻略] 42. Trapping Rain Water

題目描述

給定一個整數數組 height，每個元素表示一個柱子的高度，其中每個柱子的寬度為 1，請計算柱子之間可以容納多少雨水。

範例

範例 1：

輸入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6

範例 2：

輸入: height = [4,2,0,3,2,5]
輸出: 9

解題思路

這是一個經典的動態規劃與雙指針問題。

1. 直觀思路：
   雨水能夠存儲的量由兩側的最高柱子決定，對於每個柱子，我們需要知道：
2. • 它左側最高柱子的高度。
   • 它右側最高柱子的高度。
   • 存水量 = min(左側最高高度, 右側最高高度) - 當前高度。
2. 優化：
3. • 可以使用兩種方法：動態規劃 或 雙指針法。

解法一：暴力解法

核心思想

對於每個柱子，找到其左側和右側的最大高度，計算可以容納的雨水量。

程式碼

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        if n == 0:
            return 0

        water_trapped = 0
        for i in range(n):
            # 找到左側最大高度
            left_max = max(height[:i+1])
            # 找到右側最大高度
            right_max = max(height[i:])
            # 計算雨水量
            water_trapped += min(left_max, right_max) - height[i]
        
        return water_trapped

時間與空間複雜度

• 時間複雜度：O(n^2)
• • 對於每個柱子，我們需要遍歷一次找左、右最大高度。
• 空間複雜度：O(1)
• • 不需要額外的儲存空間。

解法二：動態規劃

核心思想

用兩個數組 left_max 和 right_max 分別保存每個柱子的左側和右側最大高度，避免暴力解法中重複計算。

步驟

1. 建立兩個數組：
2. • left_max[i] 表示 i 左側的最大高度（包含自己）。
   • right_max[i] 表示 i 右側的最大高度（包含自己）。
2. 遍歷柱子，計算每個位置的存水量。

程式碼

class Solution(object):
    def trap(self, height):
        n = len(height)
        if n == 0:
            return 0

        # 預處理左側和右側最大高度
        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i-1], height[i])

        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_trapped = 0
        for i in range(n):
            water_trapped += min(left_max[i], right_max[i]) - height[i]
        
        return water_trapped

時間與空間複雜度

• 時間複雜度：O(n)
• • 需要兩次遍歷計算 left_max 和 right_max，以及一次遍歷計算雨水量。
• 空間複雜度：O(n)
• • 額外使用了 left_max 和 right_max 數組。

解法三：雙指針法

核心思想

使用兩個指針 left 和 right 來替代 left_max 和 right_max 數組，只需維護當前的左右最大高度即可。

步驟

1. 使用雙指針 left 和 right，分別指向數組的開頭和結尾。
2. 維護左右最大高度 left_max 和 right_max。
3. 如果左側最大高度小於右側最大高度：
4. • 判斷當前柱子是否可以存水：left_max - height[left]。
   • 然後移動 left 指針。
4. 如果右側最大高度小於左側最大高度：
5. • 判斷當前柱子是否可以存水：right_max - height[right]。
   • 然後移動 right 指針。

程式碼

class Solution(object):
    def trap(self, height):
        n = len(height)
        if n == 0:
            return 0

        left, right = 0, n - 1
        left_max, right_max = 0, 0
        water_trapped = 0

        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water_trapped += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water_trapped += right_max - height[right]
                right -= 1

        return water_trapped

時間與空間複雜度

• 時間複雜度：O(n)
• • 雙指針從頭到尾只遍歷一次數組。
• 空間複雜度：O(1)
• • 只使用了常數級別的額外變量。

結論

1. 雙指針法 是最優解，時間與空間複雜度均表現優秀。
2. 動態規劃法 提供了清晰的分步邏輯，適合學習初期使用。
3. 暴力解法 雖然直觀，但不推薦在大型數組中使用。

你可以根據自己的熟悉程度選擇適合的解法！