11. Container With Most Water

題目 / Problem

中文： 給你一個長度為 n 的整數陣列 height。畫出 n 條垂直線，其中第 i 條線的兩個端點分別是 (i, 0) 與 (i, height[i])。

找出兩條線，使它們與 x 軸一起組成的容器能裝下最多的水。回傳這個最大水量。注意容器不能傾斜。

English: You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container that holds the most water. Return that maximum water amount. The container cannot be slanted.

Constraints: - n == height.length - 2 <= n <= 10^5 - 0 <= height[i] <= 10^4

Example: - Input: height = [1,8,6,2,5,4,8,3,7] - Output: 49 - 解釋 / Explanation：選擇 index 1 (高 8) 與 index 8 (高 7)。寬度 = 8 - 1 = 7，較矮的牆高度 = min(8, 7) = 7，面積 = 7 × 7 = 49。

名詞解釋 / Glossary

• 雙指針 / Two Pointers：一種常見的陣列技巧，用兩個索引（通常一個從左、一個從右）同時移動以縮小搜索範圍。A common array technique using two indices (often one from the left, one from the right) that move toward each other to shrink the search space.
• 貪心 / Greedy：每一步都做出當下看起來最有利的選擇，並能證明這樣不會錯過最優解。Make the locally best choice at each step, when we can prove this never discards the optimal answer.
• 容器面積 / Container Area：兩條垂直線與 x 軸圍成的矩形水量，計算公式為 min(left_height, right_height) × (right_index - left_index)。寬度是兩線間的距離，高度由較矮的那條線決定（水會從矮的那邊溢出）。The rectangle of water trapped between two vertical lines and the x-axis: min(left_height, right_height) × (right_index - left_index). Width is the distance between the lines; height is limited by the shorter line (water spills over the shorter side).
• 暴力法 / Brute Force：枚舉所有可能的組合 — 這裡是所有 (i, j) 對 — 然後挑最佳。簡單但通常太慢。Enumerate every possible combination — here every (i, j) pair — and pick the best. Easy but usually too slow.
• 不變量 / Invariant：演算法執行過程中始終保持為真的一個性質，用來證明演算法的正確性。A property that always holds during the algorithm's execution; used to prove correctness.

思路

最直覺的做法是暴力法：枚舉每一對 (i, j)，計算它們組成容器的水量 min(height[i], height[j]) × (j - i)，取最大值。這需要 O(n²) 的時間，當 n = 10^5 時運算量達 10^10，明顯會超時。

我們改用雙指針：設 left = 0、right = n - 1，先計算當前面積。接下來要決定移動哪一個指針。關鍵觀察是：面積由較矮的那條線決定。假設 height[left] < height[right]，如果我們移動 right 向左，那麼寬度一定變小，而高度仍然受限於 height[left]（甚至更矮），所以面積一定不會變大。因此移動較矮的指針才有可能找到更大的面積——這是一個貪心決策，雖然不保證下一步變大，但保證了「不移動矮邊永遠不會更好」。每一步排除掉的所有可能性都不可能比當前更優，所以我們不會錯過答案。指針相遇時演算法結束，總共只需 O(n) 時間。

The naive approach is brute force: try every pair (i, j), compute min(height[i], height[j]) × (j - i), and keep the maximum. That's O(n²), which for n = 10^5 blows past the time limit.

Instead we use two pointers starting at the ends: left = 0, right = n - 1. The area is bounded by the shorter of the two lines, because water spills over the lower edge. Now ask: which pointer should we move? Suppose height[left] < height[right]. If we move right inward, the width shrinks and the height is still capped by height[left] (or something even smaller), so the area cannot grow. The only way to possibly improve is to move the shorter pointer inward, hoping for a taller line that compensates for the lost width. This is a greedy choice: we discard pairs that provably cannot beat the current best, so we never miss the optimum. We stop when the pointers meet, giving a clean O(n) algorithm.

逐步走查 / Walkthrough

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7], indices 0..8.

Initialize left = 0, right = 8, best = 0.

Final answer: 49 ✓

Solution — C

/*
 * 演算法 / Algorithm:
 *   雙指針從兩端往中間掃描，每步計算當前面積並更新最大值，
 *   然後移動較矮的那一邊（移動較高的一邊絕不可能變大）。
 *   Two pointers from both ends; each step compute area, update max,
 *   then move the shorter side (moving the taller side can never help).
 *   Time O(n), Space O(1).
 */

int maxArea(int* height, int heightSize) {
    int left = 0;                                  // 左指針從 0 開始 / left pointer starts at 0
    int right = heightSize - 1;                    // 右指針從最後一格 / right pointer at last index
    int best = 0;                                  // 紀錄目前最大面積 / track the best area so far

    while (left < right) {                         // 當兩指針未相遇就繼續 / loop until pointers meet
        int h_left = height[left];                 // 讀取左邊高度 / read left height (array indexing)
        int h_right = height[right];               // 讀取右邊高度 / read right height
        int minH = h_left < h_right ? h_left : h_right;  // 較矮的牆決定水位 / shorter wall caps the water
        int width = right - left;                  // 兩線間的距離 = 寬 / horizontal distance = width
        int area = minH * width;                   // 矩形面積 / rectangle area

        if (area > best) {                         // 比已知最大還大就更新 / update if better
            best = area;                           // 更新最佳值 / save new best
        }

        if (h_left < h_right) {                    // 左邊較矮 / left side is the limiting one
            left++;                                // 把左指針往右移一格 / advance left inward
        } else {                                   // 右邊較矮或同高 / right is shorter or equal
            right--;                               // 把右指針往左移一格 / advance right inward
        }
        // 註：相等時移動哪邊都一樣 — 兩種情況下，剩下的另一邊都不可能配出更大面積。
        // Note: on ties either side works — neither pairing with the other end can beat current area.
    }

    return best;                                   // 回傳答案 / return the max area
}

Solution — C++

/*
 * 演算法 / Algorithm:
 *   與 C 版本相同：雙指針從兩端往中間，每步算面積、移動較矮的一邊。
 *   Same as the C version: two pointers shrinking inward, always
 *   moving the shorter side. Time O(n), Space O(1).
 */

#include <vector>      // std::vector — 動態陣列容器 / dynamic array container
#include <algorithm>   // std::max, std::min — 比較工具 / comparison helpers

class Solution {
public:
    int maxArea(std::vector<int>& height) {        // LeetCode 給的是 vector<int>& / signature uses vector reference
        int left = 0;                              // 左指針 / left pointer
        int right = static_cast<int>(height.size()) - 1;  // 右指針；size() 回傳 size_t (unsigned)，先轉 int 避免比較警告 / cast to int to avoid signed/unsigned warning
        int best = 0;                              // 目前最大面積 / current best area

        while (left < right) {                     // 指針未相遇就繼續 / loop while pointers haven't met
            int h = std::min(height[left], height[right]);  // 較矮的牆高 / shorter wall height
            int w = right - left;                  // 寬度 / width
            best = std::max(best, h * w);          // 若更大就更新 / take the max with current

            if (height[left] < height[right]) {    // 左邊較矮 / left is the bottleneck
                ++left;                            // 前置遞增更習慣 / prefix increment is idiomatic in C++
            } else {                               // 右邊較矮或相等 / right is shorter or equal
                --right;                           // 右指針往左移 / move right inward
            }
        }

        return best;                               // 回傳結果 / return the answer
    }
};

複雜度 / Complexity

• Time: O(n) — 兩個指針各自最多走 n 步，加起來總移動次數不超過 n，所以是線性的。Each pointer moves inward at most n times in total before they meet, so the loop runs at most n iterations.
• Space: O(1) — 只用了幾個整數變數（left, right, best），與輸入大小無關。Only a constant number of integer variables are used regardless of input size.

Pitfalls & Edge Cases

• 暴力法會超時 / Brute force TLEs：O(n²) 在 n = 10^5 時要做 ~10^10 次運算，遠超 LeetCode 的時間限制。必須用 O(n) 的雙指針。Brute force is too slow at the upper constraint; you must use two pointers.
• 移動較高那邊是錯的 / Moving the taller side is wrong：很多初學者直覺會「保留矮的試試看」，但這樣寬度減少而高度仍受矮邊限制，面積一定不會更大。要移動的是較矮的那邊。A common bug: moving the taller pointer can never increase the area (width drops, height still capped by the shorter side).
• 高度的計算是 min 不是 max / Height uses min, not max：水會從較矮的一邊溢出，所以容器高度由較矮的牆決定。寫成 max 是經典錯誤。Water spills over the shorter wall, so the container height is min(left, right). Using max is a classic mistake.
• 整數溢位 / Integer overflow：最壞情況 height[i] = 10^4，n = 10^5，最大面積約 10^4 × 10^5 = 10^9，仍在 32-bit int 範圍內（上限約 2.1 × 10^9），所以本題 int 就夠用。Maximum area fits in a 32-bit int here, but in general when widths and heights are large you may need long long.
• 空容器情況 / Tiny input：題目保證 n >= 2，所以不需要特別處理 n < 2。while (left < right) 在 n == 2 時剛好跑一次。Constraints guarantee n >= 2, so the loop runs at least once; no extra guard needed.
• 指針相等時的退出 / Termination：條件是 left < right（嚴格小於），當它們相遇時寬度為 0，沒有意義，應退出。使用 <= 是無意義的多餘迭代。Use strict <; at left == right width is 0 and the loop should end.