LeetCode 11：盛最多水的容器 —— 雙指針法 O(N) 完美解法

LeetCode 11 盛最多水的容器：從暴力到雙指針的演進之路

題目描述

給定 n 個非負整數 height[0...n-1]，代表坐標軸上各點的垂直線高度。找出兩條線，使其與 x 軸構成的容器能盛最多水。容器面積 = min(height[i], height[j]) * (j - i)。

三種解法演進

1. 暴力枚舉 O(N²) —— 會超時

int maxArea(vector& height) {
    int maxArea = 0;
    for (int i = 0; i < height.size(); ++i) {
        for (int j = i + 1; j < height.size(); ++j) {
            int area = (j - i) * min(height[i], height[j]);
            maxArea = max(maxArea, area);
        }
    }
    return maxArea;
}

2. 預測優化 O(N²) —— 仍超時

利用當前最大面積估算下一輪可能的最大寬度，跳過不可能超過的組合。但最壞情況仍為 O(N²)。

3. 雙指針法 O(N) —— 最優解

int maxArea(vector& height) {
    int left = 0, right = height.size() - 1;
    int maxArea = 0;
    
    while (left < right) {
        int area = (right - left) * min(height[left], height[right]);
        maxArea = max(maxArea, area);
        
        // 關鍵決策：移動較短的板
        if (height[left] < height[right])
            ++left;
        else
            --right;
    }
    return maxArea;
}

為什麼移動較短的板是正確的？

數學證明：假設 height[left] < height[right]。當前面積受限於左板高度。若保持左板不動、移動右板：

• 寬度 (right-left) 變小
• 高度仍受限於左板（≤ height[left]）
• 面積必然 ≤ 當前面積

因此，移動右板不可能獲得更大面積。只有移動左板，才有機會遇到更高的板，從而突破高度限制。同理，右板較短時移動右板。

圖解演示

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
初始：left=0(1), right=8(7) → area=8×1=8
移動左板（較短）
left=1(8), right=8(7) → area=7×7=49 ← 最大值
移動右板（較短）
left=1(8), right=7(3) → area=6×3=18
... 最終最大面積 = 49

複雜度分析

• 時間：O(N) — 每個指針最多移動 N 步
• 空間：O(1) — 僅使用常數額外空間

核心收穫

1. 雙指針法適用於「兩端向中間收斂」且決策可基於局部資訊的問題
2. 移動較短板的決策經過數學證明，保證不漏過最優解
3. 從暴力 → 優化 → 最優的思維路徑是演算法學習的標準範式

延伸變體

• LeetCode 42：接雨水 — 雙指針/單調棧/動態規劃多種解法
• LeetCode 167：兩數之和 II — 有序陣列雙指針經典應用