LeetCode Container With Most Water 雙指針貪心解法

問題

給定 n 根垂直線 x=i, y=height[i]，選兩根線與 x 軸圍成容器，使容積最大。容積 = (j-i) * min(height[i], height[j])。n ≥ 2。

貪心雙指針證明

• 初始左右指針 i=0, j=n-1，底最寬。
• 短板決定高度。移動長板不會增加高度 (仍受限於短板)，且底變窄，容積不增。
• 移動短板雖底變窄，但可能遇到更高板，從而增加高度，有機會獲得更大容積。
• 因此每次移動較短那側指針，直到相遇。

代碼 (C++)

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

複雜度

O(n) 時間，O(1) 空間。暴力 O(n²) 會超時。

關鍵點

• 雙指針向中間收縮，每步排除不可能最優的狀態。
• 等高時移動任意一側均可 (代碼移動左)。
• 適用於所有非負整數高度。