Container With Most Water
題目描述
給定整數陣列 height，第 i 條線段端點為 (i, 0) 和 (i, height[i])。找兩條線段，使其與 x 軸圍成的容器能裝最多水。
輸入：height = [1,8,6,2,5,4,8,3,7]
輸出：49（選擇 i=1, j=8，min(8,7)×7 = 49）
輸入：height = [1,1]
輸出：1
解題思路
雙指針初始化
left = 0, right = n-1，從最寬的配對開始，保證不遺漏最大寬度
計算面積
area = min(height[left], height[right]) × (right - left)，面積由較矮邊和寬度共同決定
更新最大值
maxArea = max(maxArea, area)，記錄全局最佳
移動較矮邊
height[left] < height[right] 時 left++，否則 right--。因為移動較高邊不可能增加面積
重複
直到 left ≥ right，所有有希望的配對都已檢查
程式碼
C#
public class Solution {
public int MaxArea(int[] height) {
int left = 0, right = height.Length - 1;
int maxArea = 0;
while (left < right) {
int area = Math.Min(height[left], height[right]) * (right - left);
maxArea = Math.Max(maxArea, area);
// 移動較矮的那邊
if (height[left] < height[right]) left++;
else right--;
}
return maxArea;
}
}TypeScript
function maxArea(height: number[]): number {
let left = 0, right = height.length - 1;
let maxArea = 0;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) left++;
else right--;
}
return maxArea;
}Python
def maxArea(height: list[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
left 和 right 每步至少移動一個，合計最多走 n-1 步，因此 O(n)。只用幾個變數，空間 O(1)。
邊界情況
- 只有兩條線：只有一種配對，直接計算
min(h[0], h[1]) × 1回傳 - 所有線段等高：例如
[5,5,5,5]，最寬的配對就是最大面積（5 × 3 = 15），任何縮小寬度都只會減少面積 - 包含高度為 0 的線段：0 高度的邊不貢獻面積，但演算法仍正確處理（area = 0）
圖解
圖表展示關鍵步驟：初始最寬配對 (0,8) 面積只有 8（被高度 1 拖累）。移動較矮的左邊後，新配對 (1,8) 面積跳到 49，成為最佳解。這正是「移動矮邊才有機會找到更高線段」的核心策略。
進階觀點
💡面試追問
Q: 為什麼移動較矮邊是正確的？
A: 假設 height[left] < height[right]。固定 left 時，right 往左移只會讓寬度減小，而高度仍被 height[left] 限制，面積只可能更小或相等。所以 (left, right-1), (left, right-2)... 這些配對都不可能更好，可以安全跳過。移動 left 則有機會遇到更高的線段。
Q: 跟 Trapping Rain Water 的差別？ A: 本題找單一矩形最大面積（兩條線 + x 軸）；Trapping Rain Water 計算所有凹槽能接的雨水總和。Trapping Rain Water 需要知道每個位置左右兩邊的最大高度（用前綴/後綴最大值或雙指針），本題只需兩端指針比較高度。
Q: 兩邊等高時移哪邊？ A: 移哪邊都可以。證明：假設兩邊等高 h，當前面積 = h x width。移任一邊後寬度減 1，若新邊 ≤ h 面積變小，若新邊 > h 面積仍被另一邊的 h 限制。兩邊對稱，不影響正確性。
理解測驗
🤔 為什麼從最寬的配對開始？
🤔 暴力法的時間複雜度是多少？