在 LeetCode 上的這個問題「Container With Most Water」要求我們在一個陣列中找到兩個柱子，這兩個柱子可以組成一個「容器」，而這個容器能容納最多的水。
每個柱子的高度由陣列height[]中的值決定，而容器的寬度則是這兩個柱子之間的距離（索引差）。要找到最大容積的容器，我們要計算容器的「容量」，公式為：容量 = min(柱子1的高度, 柱子2的高度) * 柱子1和柱子2之間的寬度
第一種解法：直觀解法（Brute Force）
這個方法比較直觀，就是用兩個迴圈暴力地計算每對柱子的容器容量，並找出最大值。
- 用兩個迴圈，第一個迴圈選擇柱子1，第二個迴圈選擇柱子2。
- 計算兩個柱子組成容器的容量。
- 保存最大容量。
時間複雜度：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），另一個指向陣列的最右端（柱子2）。
- 每次計算這兩個柱子組成的容器容量，並嘗試更新最大容量。
- 移動較矮的那個柱子指針，因為只有移動較矮的柱子才有可能找到更大的容量。
時間複雜度：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 !
