LeetCode 筆記 - 11. Container With Most Water

題目在此 11. Container With Most Water

給一個數列,表示高度。
計算出這些高度任選兩個組合出的容器的最大容量
image 32

解題思維

在這裡我們可以用 夾擠定理 先界定出上下界再來慢慢逼近
而從圖中可以看到容器的高度是由選擇的兩隻裡面,較低的那隻 決定的

所以過程中,我們可以一直更換較低的那隻來慢慢逼近出最大的面積

而實作,我進一步紀錄出現過最高的高度來進一步加速
因為底只會越來越小,如果高還沒比較高,那就不用作後面的計算了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
def maxArea(self, height: List[int]) -> int:

if not height:
return 0

left = 0
right = len(height) - 1

max_height = 0

result = 0
while left < right:

current_base = right - left
if height[left] < height[right]:
current_height = height[left]
left += 1
elif height[left] > height[right]:
current_height = height[right]
right -= 1
else:
current_height = height[right]
left += 1
right -= 1

if max_height < current_height:
max_height = current_height

result = max(result, current_height * current_base)

return result

也許你也會想看看