題目連結(https://leetcode.com/problems/container-with-most-water/description/?envType=daily-question&envId=2025-10-04)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.
Notice that you may not slant the container.

又回來解每日一題了，昨天有一題 hard 跟體積相關覺得複雜沒解出來，中斷連勝了嗚嗚

1. Repeat（題目重複確認）

• 輸入：長度為 n 的整數陣列 height ，表示有一連串的儲水量，需要在其中取兩點，再做出(i, 0) , (i, height[i]) 構成的邊
• 輸出：最大容器可承裝的數量（即為長條圖下面積）
• 前提：
  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

2. Examples（舉例確認理解）

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
7*7(第二和最後一位）寬度是7, 然後取比較小的高＝７

3. Approach（解題思路）

方法 1：雙層迴圈模擬法

• 由左往右遍歷所有組合，但 code 沒辦法實行
• 時間複雜度：O(n^2)
• 空間複雜度：O(1)

方法 2：雙指針

• 先從如何求面積著手，需要求寬和高
  • 寬：右邊索引減去左邊、高：左右兩條垂直線取短的
  • 不能 greedy 重點是寬和高並非分別取最佳解，而是要由 area去比較歷史最佳值
• 時間複雜度：O(n)
• 空間複雜度：O(1)

4. Code（C++）

實際情況跑不動

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxwater = 0;
        int n = height.size() - 1;
        
        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int width = j - i;
                int h = min(height[i], height[j]);
                int area = width * h;
                maxwater = max(maxwater, area);
            }
        }
        return maxwater;
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int maxwater = 0;
        while(l < r){
            int width = r - l; //從最大範圍的 x 開始檢查
            int h = min(height[l], height[r]);
            int area = width * h;
            maxwater = max(maxwater, area);
            if(height[l] < height[r]){
                l++; //左邊的高度較矮，往右移動
            }
            else{
                r--;
            }
        }
        return maxwater;
    }
};    

5. Test 範例

[1, 8, 6, 2, 5, 4, 8, 3, 7]
 ↑                       ↑
left=0                right=8

面積 = (8-0) × min(1,7) = 8×1 = 8
移動 left (因為 1 < 7)

   [1, 8, 6, 2, 5, 4, 8, 3, 7]
       ↑                    ↑
    left=1              right=8

面積 = (8-1) × min(8,7) = 7×7 = 49 ✓ 最大值

6. 相關題目與延伸概念

**Maximum Tastiness of Candy Basket Medium**

**House Robber IV Medium**

7. 補充：語法＆注意事項

此題的雙指針想法

• 從兩端開始，寬度最大
• 每次移動較短的那邊（因為移動較長的沒有意義）
• 持續記錄最大面積
• 典型的取左右邊界，分別往中間移動取出最適合邊界，跟滑動視窗法不太一樣

[a, b, c, d, e, f, g]
    [-----]           ← 窗口向右滑動
       [-----]        ← 保持連續性
          [-----]     

特點: left 和 right 只能向右移動（單調性）

[a, b, c, d, e, f, g]
 ↑                 ↑   ← 從兩端相向
    ↑           ↑      ← 任意移動
       ↑     ↑         

特點: 指針可以相向、同向、跳躍移動

模板

int left = 0, right = 0;
while (right < n) {
    // 擴大窗口
    window.add(arr[right]);
    right++;
    
    // 收縮窗口
    while (需要收縮) {
        window.remove(arr[left]);
        left++;
    }
}

int left = 0, right = n - 1;
while (left < right) {
    if (條件滿足) {
        return 結果;
    } else if (某條件) {
        left++;
    } else {
        right--;
    }
}

ps. 部分內容經 AI 協助整理