11. Container With Most Water

題目描述

題目連結：11. Container With Most Water

給定一個整數陣列 height，其中每個元素代表一個點的高度。這些點位於 x 軸上，每個點的 x 座標對應於它們在陣列中的索引。繪製 n 條垂直線，垂直線的兩端分別為 \((i, 0)\) 和 \((i,height[i])\)。

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

注意：你不能傾斜容器，且陣列中的每個元素都大於等於 0。

解題思路

• 本題需要計算兩條垂直線與水平線構成的容器所能容納的最大水量。
• 因為水量是由底部的長度乘上較矮的兩邊的高度來決定，因此我們可以從底部的兩端開始，逐步向內縮短底部長度。
• 只有當其中一邊的牆變高的時候，才有可能產生更大的體積。
• 所以我們可以從最外部開始尋找更高的邊，這樣就可以在只遍歷一次的情況下找到最大體積。

解題過程

1. 設定兩個指標 i 和 j，分別指向陣列的最左端和最右端。
2. 設定一個變數 ans 用於儲存最大容積。
3. 使用一個迴圈，當 i 小於 j 時繼續執行：
   • 計算 height[i] 和 height[j] 中較小的高度作為 currentHeight。
   • 計算目前的容積 currentHeight * (j - i)，並更新最大容積 ans。
   • 如果 height[i] 小於等於 currentHeight，則指標 i 向內移動一位。
   • 如果 height[j] 小於等於 currentHeight，則指標 j 向內移動一位。
4. 回傳 ans。

程式碼

class Solution {
public:
    int maxArea(vector<int>& height) {
        const int n = height.size();
        int i = 0;
        int j = n - 1;
        int ans = 0;

        while (i < j) {
            int currentHeight = min(height[i], height[j]);
            ans = max(ans, currentHeight * (j - i));

            while (i < j && height[i] <= currentHeight) {
                i += 1;
            }
            while (i < j && height[j] <= currentHeight) {
                j -= 1;
            }
        }
        return ans;
    }
};

複雜度分析

• 時間複雜度：O(n)，只需遍歷一次陣列，因此時間複雜度為 O(n)，其中 n 是陣列的長度。
• 空間複雜度：O(1)。