leetcode | Medium | 11.Container With Most Water

LeetCode | Medium | 11.Container With Most Water

在 LeetCode 上的這個問題「Container With Most Water」要求我們在一個陣列中找到兩個柱子，這兩個柱子可以組成一個「容器」，而這個容器能容納最多的水。
每個柱子的高度由陣列 height[] 中的值決定，而容器的寬度則是這兩個柱子之間的距離（索引差）。要找到最大容積的容器，我們要計算容器的「容量」，公式為：
容量 = min(柱子1的高度, 柱子2的高度) * 柱子1和柱子2之間的寬度

第一種解法：直觀解法（Brute Force）

這個方法比較直觀，就是用兩個迴圈暴力地計算每對柱子的容器容量，並找出最大值。

1. 用兩個迴圈，第一個迴圈選擇柱子1，第二個迴圈選擇柱子2。
2. 計算兩個柱子組成容器的容量。
3. 保存最大容量。

時間複雜度：O(n^2)

這是因為我們要遍歷陣列中的每一對柱子，時間複雜度是平方級的。

C++程式碼：

class Solution {
public:
    int maxArea(vector<int>& height) {
        
        int maxArea = 0;
        int n = height.size();

        // 雙迴圈遍歷每對柱子
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // 計算這對柱子的容積
                int area = min(height[i], height[j]) * (j - i);
                // 更新最大容積
                maxArea = max(maxArea, area);
            }
        }

        return maxArea;
    }
};

解釋：

• 外層迴圈選擇柱子1，內層迴圈選擇柱子2。
• 每次計算容量，並更新最大容量 maxArea。
• 雖然這種方法很容易理解，但效率較低。

第二種解法：雙指針法（Optimal Solution）

優化的解法可以使用「雙指針」，時間複雜度為 O(n)。

1. 設定兩個指針，一個指向陣列的最左端（柱子1），另一個指向陣列的最右端（柱子2）。
2. 每次計算這兩個柱子組成的容器容量，並嘗試更新最大容量。
3. 移動較矮的那個柱子指針，因為只有移動較矮的柱子才有可能找到更大的容量。

時間複雜度：O(n)

這是因為我們只需要遍歷陣列一次，每次根據柱子的高度移動指針。

C++程式碼：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0;                   // 左指針
        int right = height.size() - 1;  // 右指針

        while (left < right) {
            // 計算當前容器的容量
            int area = min(height[left], height[right]) * (right - left);
            // 更新最大容積
            maxArea = max(maxArea, area);

            // 移動較矮的柱子
            if (height[left] < height[right]) {
                ++left;
            } else {
                --right;
            }
        }

        return maxArea;
    }
};

解釋：

• 我們從兩端開始，利用兩個指針 left 和 right 計算當前容器的容量。
• 每次移動指針時，只移動較矮的那一端，這樣做是因為我們嘗試增大容器的容量（移動較矮的那端有可能找到更高的柱子）。
• 最後當指針相遇時，我們就得到了最大容積。

以上是 Hua 在 LeetCode 的解題分享，有想法或是建議歡迎在底下討論。
Day Day Good, Day Day Up !