---
title: "11. Container With Most Water"
url: "https://laigary.com/interview/coding/11-container-with-most-water"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-25"
tags: ["Greedy", "Two Pointers"]
---

# 11. Container With Most Water

[11\. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)

給一排高度不同的直線，任選兩根當作水桶的兩片壁，問能裝的最大水量。水量 = 兩根的距離（底邊）× 兩根中較矮的那根（水位）。

## 思路

**先從暴力解出發**：枚舉所有的配對，$O(n^2)$，然後取最大值。這個一定寫得出來，而且它給了一個好起點 —— 從暴力解往下優化才有東西可以講。

接著看核心想法，這是一句俗諺：**水桶的最大容量決定於最矮的一邊**。

題目給出的正是水桶高度，只是俗諺中的水桶，底部的面積都一樣；這個題目裡面，我們有不同的水桶底邊與水桶壁高度的組合。

所以我們就從左右兩端向中間逼近。逼近的關鍵觀察是：**不管移動哪一個指針，底邊都一定變短。** 底邊只會變差，那唯一還能變好的因子就是高度 —— 於是策略很清楚：把矮的那邊丟掉，賭中間會出現更高的壁。

### 為什麼丟掉矮的那邊不會漏掉答案

這是這題真正的核心 —— 「怎麼知道往中間收的時候沒跳過真正的答案？」理由是一個交換論證：

假設現在 `height[left] < height[right]`。對任何夾在中間的 `j`（`left < j < right`），配對 `(left, j)` 的面積是 `min(height[left], height[j]) × (j - left)`：

- **底邊**一定比現在小，因為 `j - left < right - left`
- **水位**一定不超過現在，因為 `min(height[left], height[j]) ≤ height[left]`，而 `height[left]` 正是現在的水位

兩個因子都不可能變好，所以 **`left` 不可能出現在任何比現在更好的答案裡**，可以安全丟掉。反過來說，如果丟掉的是高的那邊，這個論證就不成立了 —— 高的那邊還可能跟中間某根更矮但距離仍夠遠的柱子組出更大面積。

想通這一段，這題就從「我記得這個 trick」變成「我能證明它是對的」。

## 解題方向

```python
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        max_area = 0
        while left < right:
            width = right - left
            max_area = max(max_area, min(height[left], height[right]) * width)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area
```

每一輪都先算完當前的面積再移動指針，順序不能顛倒 —— 否則會漏掉當前這組配對。

**兩邊一樣高的時候往哪邊移？** 這份程式碼走 `else` 分支移右邊。移左邊也可以，答案完全相同：兩邊一樣高時，上面那個論證對兩邊同時成立，所以丟哪一邊都不會漏答案。

## 補充

**同樣是對撞指針的題**：[167. Two Sum II](/interview/coding/167-two-sum-ii-input-array-is-sorted)（和太小就移左、太大就移右）、[15. 3 Sum](/interview/coding/15-3-sum)（固定一個數再對撞剩下的區間）、[125. Valid Palindrome](/interview/coding/125-valid-palindrome)（兩端往中間比對）。共同點都是「有一個單調的量，讓你每一步都能安全丟掉一邊」，見 [Two Pointers 模板](/interview/coding/two-pointers-template)。

**別跟 [42. Trapping Rain Water](/interview/coding/42-trapping-rain-water) 搞混。** 兩題的圖看起來幾乎一樣，但問的是完全不同的事：

| | 問什麼 | 答案的形狀 |
|---|---|---|
| 11 Container With Most Water | 挑**兩根**柱子當桶壁，最多裝多少 | 一個配對 |
| 42 Trapping Rain Water | 整片地形的**所有凹陷**總共積多少水 | 每一格的貢獻之和 |

11 可以丟掉矮的那邊，因為只需要找一個最佳配對；42 每一格都要算，所以需要記住「左右兩側的最高值」，那是另一套解法（前綴最大值或單調棧）。

## 複雜度

- 時間 $O(n)$ — 兩個指針各自單向移動，總共走完陣列一次
- 空間 $O(1)$ — 只有兩個索引和一個最大值

其中 $n$ 是柱子的數量。作為對照，暴力枚舉所有配對是 $O(n^2)$ 時間、$O(1)$ 空間。