LeetCode 11: Container With Most Water

這題是之前演算法課程的作業，所以就當作複習一下。當初有想要找「找兩條最高的線配對」，但很快就發現最高的兩條不一定距離最遠，最大面積是高度乘以寬度，沒辦法只看高度。

題目

題目連結：LeetCode 11. Container With Most Water

給定一個整數陣列 height，其中 height[i] 代表第 i 條線的高度，找出兩條線，使它們與 x 軸圍成的容器能裝最多的水，回傳最大容積。

Example:

• Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

• Output: 49

• Input: height = [1, 1]

• Output: 1

核心思路

容積由較矮的那條線決定：

$\text{area} = \min(\text{height}[left], \text{height}[right]) \times (right - left)$

雙指標從兩端出發，每輪計算一次面積後，把較矮的那邊往內移。

這樣做是因為已知寬度要縮短了，唯一能增加面積的機會就是提升高度，如果移動較高的那邊只會讓高度維持不變或更差，不可能更好。所以每次都移動較矮的一邊，才有機會找到更高的線來彌補縮短的寬度。

走一遍範例

用 height = [1, 8, 6, 2, 5, 4, 8, 3, 7] 跑前幾步：

最終答案為 49。

陷阱與注意事項

• 面積是 min(height[left], height[right]) * (right - left)，不是 max，容積由短的那邊決定。
• 等高時移動哪邊都一樣，不影響正確性，程式碼中用 else: left += 1 統一處理即可。
• 迴圈條件是 left < right，不是 <=，兩個指標指到同一條線時就停止。

程式碼

from typing import Listdef maxArea(height: List[int]) -> int:    left = 0    right = len(height) - 1    max_area = 0    while left < right:        area = min(height[left], height[right]) * (right - left)        max_area = max(max_area, area)        if height[left] > height[right]:            right -= 1        else:            left += 1    return max_area

複雜度

• 時間複雜度：$O(n)$。left 和 right 各自最多移動 $n$ 次，兩者合計最多走 $n$ 步。
• 空間複雜度：$O(1)$。只用了 left、right、max_area 三個常數變數。

小結

這題的關鍵是理解「移動較矮邊的邏輯」：寬度已經縮短，必須想辦法提升高度，而瓶頸在矮的那邊，所以移動較矮邊才是唯一有意義的選擇。

類似的雙指標夾擊思維也出現在 15. 3Sum 和 42. Trapping Rain Water，可以一起練習。