今天分享的題目來源於 LeetCode 第 11 號問題：盛最多水的容器。這是一道可以使用 雙指針 的技巧來解題的經典題目。
題目描述
給定 n 個非負整數 a1，a2，…，an，每個數代表座標中的一個點 (i, ai) 。畫 n 條垂直線，使得垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
注意： 你不能傾斜容器，n 至少是2。
圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
示例:
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
題目解析
定義 i 和 j 兩個指針分別指向數組的左右兩端，然後兩個指針向中間搜索，並且更新面積最大值 res，直到 i == j 時返回 res。
其中 容器裝水量的算法是找出左右兩個邊緣中較小的那個乘以兩邊緣的距離。
動畫描述
代碼實現
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j){
res = height[i] < height[j] ?
Math.max(res, (j - i) * height[i++]):
Math.max(res, (j - i) * height[j--]);
}
return res;
}
}
複雜度分析
- 時間複雜度 O(N)，雙指針遍歷一次底邊寬度 N 。
- 空間複雜度 O(1)，指針使用常數額外空間。