盛最多水的容器：Swift 解法與思路分析
📌 問題描述
給定一個長度為 n 的整數數組 height，每個元素表示在橫坐標 i 處的一條垂直線段的高度。任意兩條線段和 x 軸構成一個容器，該容器可以裝水，水量的大小由較短的那條線段和兩線之間的距離決定。
請你找出其中能夠容納最多水的兩條線，并返回它們之間形成容器所能容納的最大水量。
示例：
輸入: height = [1,8,6,2,5,4,8,3,7]
輸出: 49
容器的兩條邊是第 2 條線（高度為 8）和第 9 條線（高度為 7），它們之間的距離是 7，所以最大面積是 min(8,7) * (8 - 1) = 7 * 7 = 49。
🐢 暴力解法（僅供參考）
在講雙指針之前，我們也可以從最樸素的方式思考問題：枚舉所有可能的兩條線段，計算它們之間可以裝多少水，最后取最大值。
這種方式雖然思路直觀，但時間復雜度為 O(n^2)，在數據量大時效率很低。
Swift 實現：
func maxAreaBruteForce(_ height: [Int]) -> Int {var maxArea = 0let n = height.countfor i in 0..<n {for j in i+1..<n {let h = min(height[i], height[j])let w = j - ilet area = h * wmaxArea = max(maxArea, area)}}return maxArea
}
雖然簡單，但這種方法會超時，不推薦在面試中使用，適合用于驗證答案或學習過程中的參考實現。
💡 解題思路
這是一個典型的雙指針問題。
我們可以從數組的兩端開始，使用兩個指針分別指向最左和最右的線段。每次計算它們之間的容器所能容納的水量，然后移動其中較短的一側。
移動較短的一側的原因是：水的高度是由較短的那條線決定的，移動較長的一側不會獲得更大的容積，但移動較短的一側可能會找到一條更高的線，從而提升水量。
步驟如下：
- 初始化兩個指針
left = 0，right = height.count - 1。 - 計算當前的水量：
min(height[left], height[right]) * (right - left)。 - 更新最大水量。
- 移動較短邊的指針（如果左邊短，則
left += 1，否則right -= 1）。 - 重復上述步驟，直到兩個指針相遇。
💻 Swift 代碼實現
func maxArea(_ height: [Int]) -> Int {var left = 0var right = height.count - 1var maxArea = 0while left < right {let h = min(height[left], height[right])let w = right - leftlet area = h * wmaxArea = max(maxArea, area)// 移動較短的那一側if height[left] < height[right] {left += 1} else {right -= 1}}return maxArea
}
📊 時間與空間復雜度分析
-
時間復雜度：O(n)
每個指針最多走一次，所以是線性時間復雜度。 -
空間復雜度：O(1)
只使用了常數級別的額外變量。
? 優化建議
這個解法已經是最優解法之一。如果你嘗試使用兩層 for 循環暴力解法，時間復雜度將會是 O(n^2)，在輸入規模較大時效率非常低。而雙指針方法能夠在線性時間內求解，是在面試中非常推薦的策略。
🧪 測試一下
let test = [1,8,6,2,5,4,8,3,7]
let result = maxArea(test)
print("最大水量是：\\(result)") // 輸出 49
🏁 總結
- 本題的核心在于意識到兩條邊之間的水量只與短邊有關，因此采用雙指針、移動短邊是一種非常聰明且高效的方式。
- 這是 LeetCode 中非常經典的一道題，也能很好地鍛煉你的思維方式是否具備“從整體最優轉向局部策略”的能力。
如果你喜歡這樣的算法題解風格，歡迎點贊、評論或者關注我一起交流 Swift、算法與面試技巧！
)
