[LeetCode解題攻略] 11. Container With Most Water

這篇文章將介紹 LeetCode 題目 11. Container With Most Water。這是一道經典的雙指針問題，題目要求我們找到容器可以盛最多水的情況，並幫助我們理解如何通過移動左右指針來最大化結果。

題目概述

給定一個整數數組 height，每個數字代表不同位置的垂直線高度。選擇兩條線與 x 軸組成一個容器，計算該容器能裝最多的水量。

範例：

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

思路分析

這道題目要求我們找到能夠盛最多水的兩條垂直線，根據盛水的物理公式：

水量=min⁡(左邊界高度,右邊界高度)×(右邊界索引−左邊界索引)

要想得到最大水量，我們的目標是找到合適的左右邊界，使得「最小高度」與「距離」的乘積最大。

雙指針法

這道題的最佳解法是 雙指針法。我們從數組的兩端出發，逐步向內收縮指針，並在每一步計算出水量的大小。這樣可以在遍歷一次數組的情況下求得最大水量。

因為水量是由左右兩邊的最小高度決定的。假如我們移動高度較小的指針，或許能找到更高的邊界並形成更大面積；而如果移動高度較大的指針，則無法增大水量，因為水量取決於最小高度。因此，我們每次選擇移動高度較小的指針，來嘗試增加水量。

步驟

1. 初始化左右指針，分別指向數組的兩端。
2. 計算當前左右邊界能容納的水量，更新最大水量。
3. 移動較小的指針，嘗試找到更高的邊界。
4. 重複上述步驟，直到左右指針相遇。

實作 (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 題目的解法！