LeetCode 11 Container With Most Water：盛最多水的容器

題目翻譯

給定 n 個非負整數 a1..an，代表座標 (i, ai) 處的垂直線。找兩條線與 x 軸構成容器，盛水最多。不能傾斜容器。

解法演進

暴力法 O(N²) - 超時

雙層迴圈枚舉所有線對，計算面積 min(h[i],h[j]) * (j-i)。

雙指針法 O(N) - 最優

左右指針 left=0, right=n-1 向中間收縮。面積受限於較短線。關鍵洞察：固定較短線，移動較長線無法增加面積（寬度減小，高度不增）。唯有移動較短線，才可能遇到更高線從而增加面積。因此每次移動較短線那側指針。

C++ 實現

class Solution {
    int area(int i, int j, int ai, int aj) {
        return abs(i - j) * min(ai, aj);
    }
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int ans = area(left, right, height[left], height[right]);
        while (left < right) {
            if (height[left] < height[right]) ++left;
            else --right;
            ans = max(ans, area(left, right, height[left], height[right]));
        }
        return ans;
    }
};

正確性證明

反證法：假設最優解被跳過，則存在某步移動較長線能得更優解，但移動較長線寬度減小且高度不增，矛盾。故移動較短線策略不會遺漏最優解。