Leetcode 題目鏈接

思路

取首尾雙指針和水量如下所示，設高度函數為 $h(i)$，在下圖中 $h(l)<h(r)$。

觀察以 $l$ 為左邊界所能構成的其他水量，與矮的右邊界搭配結果如下。

與高的右邊界搭配結果如下。

我們可以發現水量都會變小，即無法通過當前 $l$ 獲得更大的水量，可在記錄水量后舍棄 $l$，使其右移。

如果初始 $h(l)>h(r)$, 則鏡像處理，令 $r$左移。

如果初始 $h(l)=h(r)$，任意移動均可。

此后循環分析這個過程并移動指針即可。

嚴謹證明

假設初始 $h(l)<h(r)$，當前可容納的水量記為 $c=(r?l)\times h(l)$。

$?i\in (l,r)$，$i$ 和 $l$ 作為邊界對應的可容納水量記為 c ′ = ( i ? l ) × m i n { h ( i ) , h ( l ) } c' = (i - l) \times min\{h(i),\ h(l)\} c′=(i?l)×min{h(i),?h(l)}，其中：

• $i?l<r?l$
• m i n { h ( i ) , h ( l ) } ≤ h ( l ) min\{h(i),\ h(l)\} \leq h(l) min{h(i),?h(l)}≤h(l)

故 $c^{\prime }<c$，可在記錄水量后舍棄 $l$，令 $l$ 右移，因為無法通過 $l$ 獲得更大的水量。

余下分析同上。

代碼

僅提供 java 代碼。

class Solution {public int maxArea(int[] height) {int l = 0;int r = height.length - 1;int maxCap = 0; // 待返回的最大水量while (l < r) {int cap = (r - l) * Math.min(height[l], height[r]);maxCap = Math.max(maxCap, cap);if (height[l] < height[r]) {l++;} else {r--;}}return maxCap;}
}

復雜度

時間：$\Theta (n)$
空間：$\Theta (1)$

推廣

以下皆為個人所著，兼顧了職場面試和本碩階段的學術考試。

• 附個人題解的雙指針題單
• 圖論入門
• 圖論進階

點贊關注不迷路，祝各位早日上岸，飛黃騰達！