給定整數陣列
height，其中height[i]代表第i條線的高度。找出兩條線與 x 軸構成的容器，使其能容納最多的水。回傳最大水量。
Example:
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49
Intuition
TIP
核心思路：雙指針從兩端開始，每次移動較矮的那一側，因為移動較高的一側不可能得到更大面積。
- 面積 =
min(height[left], height[right]) * (right - left) - 寬度隨指針靠近一定縮小，所以唯一能讓面積增大的方式是提升高度
- 移動較矮的指針才「有機會」遇到更高的線；移動較高的指針只會讓高度不變或更低
- 這是一個貪心策略：每步都捨棄不可能產生更大面積的選擇
Approaches
1. Brute Force — O(n^2) / O(1)
- Idea: 列舉所有
(i, j)配對，計算面積取最大值 - Time:
O(n^2)- 兩層迴圈 - Space:
O(1)
class Solution {
fun maxArea(height: IntArray): Int {
var maxWater = 0
for (i in height.indices) {
for (j in i + 1 until height.size) {
val water = minOf(height[i], height[j]) * (j - i)
maxWater = maxOf(maxWater, water)
}
}
return maxWater
}
}⭐ 2. Two Pointers (Greedy) — O(n) / O(1)
- Idea: 左右指針從兩端開始，計算面積後移動較矮的一側，直到指針相遇
- Time:
O(n)- 每步移動一個指針，共 n-1 步 - Space:
O(1)- 只用兩個指針和一個最大值變數
class Solution {
fun maxArea(height: IntArray): Int {
var left = 0
var right = height.size - 1
var maxWater = 0
while (left < right) {
val water = minOf(height[left], height[right]) * (right - left)
maxWater = maxOf(maxWater, water)
if (height[left] < height[right]) {
left++
} else {
right--
}
}
return maxWater
}
}WARNING
當 height[left] == height[right] 時，移動任一側皆可（不會漏掉最佳解）。因為若最佳解需要其中一側不動，另一側在內部一定會被遍歷到。
🔑 Takeaways
- Pattern: 相向雙指針 + 貪心，適用於「從兩端收縮、寬度遞減」類型的最佳化問題
- Key trick: 「移動較矮一側」的貪心證明——移動較高一側，高度受限於較矮方，寬度又縮小，面積必定不增