這篇文章將介紹 LeetCode 題目 11. Container With Most Water。這是一道經典的雙指針問題，題目要求我們找到容器可以盛最多水的情況，並幫助我們理解如何通過移動左右指針來最大化結果。
題目概述
給定一個整數數組height，每個數字代表不同位置的垂直線高度。選擇兩條線與 x 軸組成一個容器，計算該容器能裝最多的水量。範例：
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
思路分析
這道題目要求我們找到能夠盛最多水的兩條垂直線，根據盛水的物理公式：
水量=min(左邊界高度,右邊界高度)×(右邊界索引−左邊界索引)
要想得到最大水量，我們的目標是找到合適的左右邊界，使得「最小高度」與「距離」的乘積最大。
雙指針法
這道題的最佳解法是 雙指針法。我們從數組的兩端出發，逐步向內收縮指針，並在每一步計算出水量的大小。這樣可以在遍歷一次數組的情況下求得最大水量。
因為水量是由左右兩邊的最小高度決定的。假如我們移動高度較小的指針，或許能找到更高的邊界並形成更大面積；而如果移動高度較大的指針，則無法增大水量，因為水量取決於最小高度。因此，我們每次選擇移動高度較小的指針，來嘗試增加水量。
步驟
- 初始化左右指針，分別指向數組的兩端。
- 計算當前左右邊界能容納的水量，更新最大水量。
- 移動較小的指針，嘗試找到更高的邊界。
- 重複上述步驟，直到左右指針相遇。
實作 (Python)
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
# 計算當前水量
width = right - left
area = min(height[left], height[right]) * width
max_area = max(max_area, area)
# 移動較小的指針
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
複雜度分析
- 時間複雜度：O(n)，因為我們只需要遍歷一次數組。
- 空間複雜度：O(1)，僅用了幾個指針和變數來存儲中間結果。
總結
這道題目通過雙指針法來優化查找過程，使得能夠在線性時間內找到最大水量，這個思路在解決「雙邊界最大化」問題中非常常見，值得我們學習和應用。
希望這篇教學能幫助你掌握 Container With Most Water 題目的解法！