LeetCode 11. 盛最多水的容器：雙指針貪心證明與 O(n) 解法

題目描述

給定 n 個非負整數 height[i] 代表坐標點 (i, height[i]) 的垂直線。找出兩條線與 x 軸圍成的容器，使盛水量最大。容器面積 = min(h[left], h[right]) * (right - left)。

直觀錯誤：動態規劃/三向遷移

嘗試 dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) 但無法證明最優子結構，且存在反例：局部最優不導向全局最優。

正確貪心策略：雙指針向內收縮

• 初始 left=0, right=n-1，面積最大寬度。
• 每次移動較矮的那側指針：if (h[left] < h[right]) left++; else right--;
• 記錄過程中最大面積。

證明核心：不會漏掉最優解

假設 h[left] < h[right]。當前面積受限於 h[left]。若保留 left 移動 right，寬度減小，高度仍 ≤ h[left]，面積必不增大。只有移動較矮側，才有可能遇到更高的線，從而獲得更大面積。反之同理。

C++ 實現