題目解釋
給定一個長度為 n 的整數 array。
第 i 條線的兩個端點為 (i, 0)
和 (i, height[i])
。
回傳 container 可以儲存的最大水量。
範例
- 輸入:
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
- 輸出:
49
在這種情況下,容器可容納的最大水面積(藍色部分)為 49。
最佳解法
步驟
- 令雙指標
left
跟right
- 如果現在的乘積
curr_area
比max_area
小,就移動height[left]
與height[right]
中比較小的那個 - 開心回傳
max_area
程式碼
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while (left < right):
min_bar = min(height[left], height[right])
curr_area = (right - left) * min_bar
max_area = max(curr_area, max_area)
if height[left] <= height[right]:
left += 1
else:
right -= 1
return max_area
時間複雜度
O(n)
,n 是 height
的元素個數。
空間複雜度
O(1)
。
結語
只有我每次第一眼看到題目都會想說為啥不是 8
跟 8
配嗎…。
( 論國小面積公式沒學好的下場 😅 )
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26