11. Container With Most Water

📘 題目敘述

給定一個長度為 n 的整數陣列 height，其中 height[i] 代表在座標 i 處的一條垂直線段高度。

請找出兩條線段，使它們與 x 軸形成一個容器，並回傳這個容器所能盛裝的最大水量。

注意：容器不能傾斜。

條件限制

• n == height.length
• 2 ≤ n ≤ 10^5
• 0 ≤ height[i] ≤ 10^4

🧠 解題思路（第一直覺）

在看這題時，我的想法是：因為題目保證 height 至少有兩個元素，所以一定能形成一個容器。

我先從最左邊與最右邊各選一條線段開始，這樣可以得到目前可能的最大寬度。

容器能裝多少水，取決於兩個因素：

• 寬度：j - i
• 高度：min(height[i], height[j])

因此面積為：(j - i) * min(height[i], height[j])

所有變數

• i：左指標，從陣列最左邊開始
• j：右指標，從陣列最右邊開始
• vol：目前為止找到的最大水量
• nvol：目前 (i, j) 這組位置計算出的水量（暫存）

在固定 i 與 j 之後，我會先計算目前這組線段所形成的水量，接著再決定「要移動哪一邊的指標」。

核心判斷（這題的重點）

在 (i, j) 這個位置下：

• 容器的高度一定是 min(height[i], height[j])
• 也就是說，比較矮的那一邊會限制整個容器的高度

因此會出現兩種情況：

情況一：height[i] >= height[j]（右邊比較矮）

• 此時容器高度由 height[j] 決定
• 如果我移動左邊（比較高的那一邊）：
  • 寬度會變小
  • 高度仍然被右邊的矮線段限制
  • 面積只可能變小，不可能變大

因此我選擇：

• 將右指標往內移動：j--
• 因為只有把「比較矮的那一邊」往內推，才有機會遇到更高的線段，讓高度變大

情況二：height[i] < height[j]（左邊比較矮）

• 此時容器高度由 height[i] 決定
• 同樣地，若移動右邊（比較高的一邊）只會讓寬度變小，高度不變
• 因此我選擇將左指標往內移動：i++

嘗試尋找一條比目前 height[i] 更高的線段，以解除容器高度受限於左邊矮線的情況。

每一步在做什麼？

在每一次指標移動前：

• 先計算目前 (i, j) 的水量
• 若 nvol 大於目前的 vol，就更新最大值

接著依照「移動較矮邊」的規則，更新 i 或 j。

當 i >= j 時，代表所有可能的組合都已經考慮完成，回傳 vol 即可。

為什麼「移動比較高的那一邊」一定不會變好？

在 (i, j) 固定的情況下，容器的水量為：

(j - i) * min(height[i], height[j])

這代表一件很關鍵的事情：

• 容器的高度永遠由比較矮的那一邊決定
• 比較高的那一邊，對目前這個容器的高度其實沒有貢獻

💻 程式碼實作

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0;
        int j = height.size() - 1;
        int vol = 0;
        int nvol = 0;
        while (i < j) {
            if (height[i] >= height[j]) {
                nvol = (j - i) * height[j];
                if (vol < nvol) {
                    vol = nvol;
                }
                j = j - 1;
            } else {
                nvol = (j - i) * height[i];
                if (vol < nvol) {
                    vol = nvol;
                }
                i = i + 1;
            }
        }
        return vol;
    }
};

🔗 題目連結

https://leetcode.com/problems/container-with-most-water/