跳至主要内容

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)
標籤：
最後於 更新