題目描述:給定 n 條垂直線,第 i 條線的高度為 height[i],找出兩條線連同 x 軸所圍成的最大容水量。
解題思路:使用雙指標從兩端向中間收縮。容積由 min(height[left], height[right]) * (right - left) 決定。移動較短的那一側指標——因為移動較長的那側只會讓寬度縮短而高度不增,容積只會變小或不變;移動較短的那側則有機會找到更高的線,從而增大容積。這個貪心策略保證不會錯過最優解。
時間複雜度:O(n) — 雙指標各最多移動 n 次。
空間複雜度:O(1) — 只用兩個指標和一個結果變數。
1. Set left = 0, right = n - 1, maxWater = 0 2. While left < right: a. Compute water = min(height[left], height[right]) * (right - left) b. maxWater = max(maxWater, water) c. If height[left] < height[right]: left++ d. Else: right-- 3. Return maxWater
暴力法 O(n²):嘗試每一對直線。正確但太慢。
單調棧:可找到下一個更大元素,但對此特定問題並未改進雙指標的表現。