題目資訊

• 題目編號: 11
• 題目連結: Container With Most Water
• 主題: Array, Two Pointers, Greedy

題目敘述

你有一個整數陣列 height，其長度為 $n$。這裡有 $n$ 條垂直線繪製出來，使得第 $i$ 條線的兩個端點為 $(i, 0)$ 和 $(i, \text{height}[i])$。

找出兩條線，與 x 軸一起形成一個容器，使得該容器可以容納最多的水。

返回容器可以存儲的最大水量。

注意 你不能傾斜容器。

範例 1:

輸入: height = [1,8,6,2,5,4,8,3,7]
輸出: 49
解釋: 上述的垂直線由陣列 [1,8,6,2,5,4,8,3,7] 所表示。在此情況下，容器可容納的最大水量（藍色區域）為 49。

範例 2:

輸入: height = [1,1]
輸出: 1

約束條件:

• $n == \text{height.length}$
• $2 \leq n \leq 10^5$
• $0 \leq \text{height}[i] \leq 10^4$

直覺

解決此問題的直覺想法是找出於平面上形成最大面積的垂直線。可以有效地觀察到面積由兩條線中較短的一條和它們之間的距離決定。因此，為了最大化面積，我們應該嘗試同時最大化高度和距離。一般的做法可能涉及檢查所有可能的線對，但由於這在計算上很昂貴，因此一種更有效的方法是使用雙指針技巧，根據當前考慮的線的相對高度來調整指針。

解法

此解法採用了雙指針技巧以高效計算最大面積。兩個指針初始化於 height 陣列的兩端，代表最初的線對。演算法按照以下步驟進行：

1. 初始化最大面積：開始時將 maxWater 設為零，這將在迭代過程中記錄找到的最大面積。

2. 雙指針技術：

   • 設定 left 指針在起始位置（索引 0）和 right 指針在結束位置（索引 n-1，其中 n 是 height 陣列的長度）。

3. 計算及比較面積：

   • 當 left 指針小於 right 指針時：
     • 使用公式計算由 left 和 right 指針位置的線組成的潛在面積： $$ \text{Area} = (\text{right} - \text{left}) \times \min(\text{height}[left], \text{height}[right]) $$
     • 將其與 maxWater 比較，如果新的面積較大則更新 maxWater。

4. 調整指針：

   • 移動指向較短線的指針：
     • 如果 height[left] < height[right]，則增加 left 指針以在右側尋找可能更高的線。
     • 如果 height[left] > height[right]，則減少 right 指針以在左側尋找可能更高的線。
     • 如果兩條線高度相同，則同時增加兩個指針以探索新的範圍，任何移動都可能導致更大的面積。

5. 終止條件：當 left 指針與或超過 right 指針時，表明所有可能的容器配置皆已評估。

6. 結果：一旦迴圈結束，maxWater 會持有找到的最大面積，最終返回該值。

通過如此迭代評估面積並策略性地移動指針，演算法達到了 $O(n)$ 的最優時間複雜度，其中 $n$ 是垂直線的數量。鑑於 $n$ 可達到 $10^5$ 的限制，該效率至關重要。

程式碼

C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxWater = 0;  // 初始化最大水量儲存
        int left = 0;  // 起始指標位於陣列開頭
        int right = height.size() - 1;  // 結束指標位於陣列末尾

        // 當左指標小於右指標時進行迭代
        while (left < right) {
            // 計算當前邊界的面積並更新maxWater
            maxWater = max(maxWater, 
                           (right - left) * min(height[left], height[right]));

            // 移動指向較短線段的指標
            if (height[left] < height[right]) {
                left++;  // 將左指標向右移動
            } else if (height[left] > height[right]) {
                right--;  // 將右指標向左移動
            } else {
                // 如果兩條線高度相同，則同時移動兩個指標
                left++;
                right--;
            }
        }

        return maxWater;  // 返回找到的最大水面積
    }
};

Python

class Solution:
    def maxArea(self, height):
        maxWater = 0  # 初始化最大儲水量
        left = 0  # 起始指針在陣列的開頭
        right = len(height) - 1  # 結束指針在陣列的末尾

        # 當左指針小於右指針時進行迭代
        while left < right:
            # 計算當前邊界的區域並更新maxWater
            maxWater = max(maxWater, 
                           (right - left) * min(height[left], height[right]))

            # 移動指向較短線段的指針
            if height[left] < height[right]:
                left += 1  # 左指針向右移動
            elif height[left] > height[right]:
                right -= 1  # 右指針向左移動
            else:
                # 如果兩條線段的高度相同，則同時移動兩個指針
                left += 1
                right -= 1

        return maxWater  # 返回找到的最大水域面積

複雜度分析

• 時間複雜度: $O(n)$

該演算法使用雙指針方法，其中一個指針從數組的開頭開始，另一個指針從數組的末尾開始。在每次迭代中，至少有一個指針向另一個指針移動。由於數組中有 $n$ 個元素，並且每個元素最多被左或右指針訪問一次，因此該方法的時間複雜度為 $O(n)$。

• 空間複雜度: $O(1)$

該演算法僅使用常數量的額外空間，主要用於存儲變數如 maxWater、left 和 right。所使用的空間不依賴於輸入數組的大小，因此空間複雜度為 $O(1)$。