【LeetCode】11. 盛最多水的容器
11. 盛最多水的容器
知識點：雙指針
題目描述
給定一個長度為 n 的整數數組 height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
返回容器可以儲存的最大水量。
說明：你不能傾斜容器。
示例
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
輸入：height = [1,1]
輸出：1
解法一：雙指針
這道題目剛一看可能想用單調棧去解，類似84題那樣，把持一個單調遞減棧，但是仔細一想其實不是那個意思，單調棧往往是用來尋找下一個比自己大或者比自己小的元素，但是這道題是找最後一個比自己大的元素。所以不能去單調棧的想法去解
其實可以首尾雙指針，因為想要最大嘛，索性寬度直接就最大，那麼對於兩個指針，面積是多大呢
area = min(height[left],height[right]) * (right-left)
那這次面積求完以後該移動誰呢？想一下，應該移動兩者中小的那一個，為什麼？
- if移動小的那一個，那接下來元素if比它小，那面積就更小了，if比它大，那面積就可能會增大，所以總體來說是可能會變大的；
- if移動大的那一個，那接下來的元素if比小的那一個小，那面積就更小了，if比小的那個大，那面積還是會變小，所以總體來說肯定會變小；
綜上，所以應該移動小的那一個，直到兩者見面，然後求出最大面積。
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height)-1
max_area = 0
while left < right:
if height[left] <= height[right]:
area = height[left] * (right - left)
left += 1
else:
area = height[right] * (right-left)
right -= 1
max_area = max(max_area, area)
return max_area
