11. Container With Most Water
11. Container With Most Water是一個運用雙指標的算法,標注為 Medium 難度。 解完後回頭再看一次,發覺些蠻多額外直得注意的事情,所以就筆記一下。
思路
最簡單的是暴力解,就是把一個一個的面積遍歷出來比較
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
result = 0
for i in range(n):
left = i
right = n - 1
while left < right:
h = min(height[left], height[right])
l = right - left
area = h * l
if area > result:
result = area
right -= 1
return result
但是這解法會跳出 Time Limit Exceeded 超過時間複雜度限制,失敗的 case 是:
[0,1,2,3,4,5,...,10000,9999,9998,...,4,3,2,1] # 長度是 20000
算一下總共跑幾次:
i = 0時,內層跑n−1次i = 1時,內層跑n−2次- …
合計共 n(n−1)/2 次,上述暴力解法的時間複雜度是 O(n^2)。
20000 帶入 n(n−1)/2 得: 199990000 ~= 2 * 10^8。而常用的粗略估計 Python 每秒約 10^7 次簡單運算,所以這題 Python 大約要算 2 * 10^8/ 10^7 = 20 秒左右,難怪會超時呢。
但其實指針的移動是可以知道的,因為 area 的公式是 h*l ,那麼根據公式可以知道如果要求出最大 area 的話,h 或 l 應該是盡可能的大。而由於 l 只能縮小,所以 h 不變大,就不可能超過原來的值,所以就只能嘗試變動比較矮的指針,故:
- 如果左邊的隔板比右邊矮,就收縮左邊
- 如果右邊的隔板比左邊矮,就收縮右邊
收縮滑窗的做法,直接把暴力解的 while-loop 幹掉了,直接下降一個時間複雜維度。
解答
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
result = 0
left = 0
right = n - 1
while left < right:
l = right - left
h = min(height[left], height[right])
area = h * l
if area > result:
result = area
if height[left] > height[right]:
right -= 1
elif height[left] < height[right]:
left += 1
else:
right -= 1
left += 1
return result
時間空間複雜度
假設整數陣列 height 長度為 N :
時間複雜度: O(N)
這題最主要是可以優化到 O(N),由 Hint2. 的說法:
Try to use two-pointers. Set one pointer to the left and one to the right of the array.
Always move the pointer that points to the lower line.
關鍵是可以知道要讓哪個指針移動,這題是每次都移動較矮那條線的指標就可以了。
空間複雜度:O(1)
都是臨時變數,所占用的記憶體空間固定,都是常數級別 O(1)
