Description
給定整數陣列
height，其中height[i]代表第i條線的高度。找出兩條線與 x 軸構成的容器，使其能容納最多的水。回傳最大水量。
Example:
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49
Intuition#
核心思路：雙指針從兩端開始，每次移動較矮的那一側，因為移動較高的一側不可能得到更大面積。
- 面積 =
min(height[left], height[right]) * (right - left) - 寬度隨指針靠近一定縮小，所以唯一能讓面積增大的方式是提升高度
- 移動較矮的指針才「有機會」遇到更高的線；移動較高的指針只會讓高度不變或更低
- 這是一個貪心策略：每步都捨棄不可能產生更大面積的選擇
Approaches#
1: Brute Force#
- 概念: 列舉所有
(i, j)配對，計算面積取最大值 - 時間複雜度:
O(n^2)- 兩層迴圈 - 空間複雜度:
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)- 每步移動一個指針，共 n-1 步 - 空間複雜度:
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
}
}當
height[left] == height[right]時，移動任一側皆可（不會漏掉最佳解）。因為若最佳解需要其中一側不動，另一側在內部一定會被遍歷到。
🔑 Takeaways#
- Pattern: 相向雙指針 + 貪心，適用於「從兩端收縮、寬度遞減」類型的最佳化問題
- 關鍵技巧: 「移動較矮一側」的貪心證明——移動較高一側，高度受限於較矮方，寬度又縮小，面積必定不增