LeetCode 筆記 - 11. Container With Most Water

Posted on

題目在此 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

相關文章