【Leetcode 筆記】 11. Container With Most Water

題目解釋

給定一個長度為 n 的整數 array。
第 i 條線的兩個端點為 (i, 0) 和 (i, height[i])。
回傳 container 可以儲存的最大水量。

範例

• 輸入: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
• 輸出: 49

在這種情況下，容器可容納的最大水面積（藍色部分）為 49。

最佳解法

步驟

1. 令雙指標 left 跟 right
2. 如果現在的乘積 curr_area 比 max_area 小，就移動 height[left] 與 height[right] 中比較小的那個
3. 開心回傳 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 配嗎…。
( 論國小面積公式沒學好的下場 😅 )

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

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