1 題目描述

給定一個非負整數的數組height，每個元素代表一個垂直線，並且每個線的寬度都是1。找出兩條線，使得他們和x軸組成的容器可以容納最多的水。
（注意不可以傾斜容器）

2 解法

2.1 暴力解法

這題的暴力破解是O(N)基本上就是遍歷所有的組合，找出最大的容器。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        for i in range(n):
            for j in range(i+1, n):
                ans = max(ans, min(height[i], height[j]) * (j-i))
        return ans

2.2 Speed O(N)

從知道這是two pointer的時候就要有個認知，那就是某種程度上他是有序的，這個案例有兩個變數，在計算面積 = 距離(指標距離) * 高度(min指標值)，我們知道，距離最大的狀況下是頭跟尾，但是window縮小的時候距離只會越來越小，他是有序的。

然而這題比較困難的點是，我們要如何確保windows之外已經算過不可能有比目前最佳解還要好的前提下來縮window，因為距離是有跡可循，window縮小的時候只會更小，因此找到最大面積的關鍵是高度(min指標值)，他是一個不確定的因素，有可能window縮小時獲得更大的面積只是因為容器夠高，那我們要怎麼或得最大容器面積呢？

有三個重要概念

如果發現比max_area大的面積，就更新max_area
因為window縮小的時候，距離一定是縮短的，所以我們不避顧慮距離(指標位置)在windows之外有沒有可能有最佳解，因為我們最先計算的就是最大的距離left=0和right=len(height)-1。windows之外都是已經算過了，我們也把當前windows外的最佳解存在max_area。
在縮window時真正會影響有沒有最佳解的是高度(指標值)，決定是否要移動pointer時，只要考慮高度即可。
1. 如果 height[left] < height[right]，那麼我們就移動left，因為height[left]是最小的，所以我們要找更大的height。
2. 如果 height[left] > height[right]，那麼我們就移動right，因為height[right]是最小的，所以我們要找更大的height。
3. 如果 height[left] == height[right]，那麼我們就移動left或right都可以，因為他們都是最小的，所以我們要找更大的height。

# 初始狀態
0,1,2,3,4,5,6,7,8 (= index)
[1,8,6,2,5,4,8,3,7]
 L               R

Left pointer starts from index 0
Right pointer starts from the last index
width = right - left = 8 - 0 = 8
height = min(height[left], height[right]) = min(1, 7) = 1
area = 8 * 1 = 8

# 在這個狀況下 left vs right = 1 vs 7
# 1 < 7 所以我們移動left pointer
 0,1,2,3,4,5,6,7,8 (= index)
[1,8,6,2,5,4,8,3,7]
   L             R

Left pointer moves to next
Right pointer stays the same
current_area = 7 * 7 = 49
max_area = max(8, 49) = 49

# 在這個狀況下 left vs right = 8 vs 7
# 8 > 7 所以我們移動right pointer
 0,1,2,3,4,5,6,7,8 (= index)
[1,8,6,2,5,4,8,3,7]
   L           R

Left pointer stays the same
Right pointer moves to next
current_area = 6 * 3 = 18
max_area = max(49, 18) = 49

# 在這個狀況下 left vs right = 8 vs 3
# 8 > 3 所以我們移動right pointer
 0,1,2,3,4,5,6,7,8 (= index)
[1,8,6,2,5,4,8,3,7]
   L         R

Left pointer stays the same
Right pointer moves to next
current_area = 5 * 8 = 40
max_area = max(49, 40) = 40

# 在這個狀況下 left vs right = 8 vs 8
# 8 == 8 所以我們可以選擇移動left或是right pointer，這裡我們移動right pointer
 0,1,2,3,4,5,6,7,8 (= index)
[1,8,6,2,5,4,8,3,7]
     L       R

Left pointer moves to next
Right pointer stays the same
current_area = 4 * 6 = 24
max_area = max(49, 24) = 49

...

完整程式碼可以寫成

"""
Time: O(N)
Space: O(1)
"""
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height)-1
        max_area = -1
        while l < r:
            cur = (r-l) * min(height[l], height[r])
            max_area = max(max_area, cur)
            if height[l] > height[r]:
                r -= 1
            else:
                l += 1
        return max_area