題目描述
給定一個整數數組 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
解題思路
這是一個經典的動態規劃與雙指針問題。
- 直觀思路：
雨水能夠存儲的量由兩側的最高柱子決定，對於每個柱子，我們需要知道： - 它左側最高柱子的高度。
- 它右側最高柱子的高度。
- 存水量 = min(左側最高高度, 右側最高高度) - 當前高度。
- 優化：
- 可以使用兩種方法：動態規劃 或 雙指針法。
解法一：暴力解法
核心思想
對於每個柱子，找到其左側和右側的最大高度，計算可以容納的雨水量。
程式碼
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 分別保存每個柱子的左側和右側最大高度，避免暴力解法中重複計算。
步驟
- 建立兩個數組：
- left_max[i] 表示 i 左側的最大高度（包含自己）。
- right_max[i] 表示 i 右側的最大高度（包含自己）。
- 遍歷柱子，計算每個位置的存水量。
程式碼
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 數組，只需維護當前的左右最大高度即可。
步驟
- 使用雙指針
left和right，分別指向數組的開頭和結尾。 - 維護左右最大高度
left_max和right_max。 - 如果左側最大高度小於右側最大高度：
- 判斷當前柱子是否可以存水：left_max - height[left]。
- 然後移動 left 指針。
- 如果右側最大高度小於左側最大高度：
- 判斷當前柱子是否可以存水：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)
- 只使用了常數級別的額外變量。
結論
- 雙指針法 是最優解，時間與空間複雜度均表現優秀。
- 動態規劃法 提供了清晰的分步邏輯，適合學習初期使用。
- 暴力解法 雖然直觀，但不推薦在大型數組中使用。
你可以根據自己的熟悉程度選擇適合的解法！
