給你 n 個非負(fù)整數(shù) a1，a2逮矛，...，an转砖，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 须鼎。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) 府蔗。找出其中的兩條線晋控，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器姓赤。
示例 ：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]赡译。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49不铆。
解法一
自己沒看答案前自己的做法蝌焚，也是很多人最容易想到的做法，就是分別列舉出所有可能的容器并且比較大小狂男，但是時間復(fù)雜度是O(n^2)综看，沒有通過力扣的時間要求。
def maxArea1(height):
"""超出時間限制"""
n = len(height)
s = 0
for i in range(n - 1):
for j in range(i + 1, n):
t = min(height[i], height[j]) * (j - i)
if t > s:
s = t
return s
解法二
參考力扣官方答案岖食，就是采用雙指針的做法红碑，用左右指針分別指向數(shù)組的兩邊，然后逐步的往中間移動指針泡垃，每次移動值小的那邊的指針析珊，因為只有這樣后面的裝的水才有可能最多。
自己之前也想到了用雙指針蔑穴，也相到了從左右往中間移動忠寻，但是不知道怎么移動指針，以后還是要多觀察嘗試存和，記住滿足某個條件才移動指針奕剃，左右指針也沒必要同時移動。
def maxArea2(height):
l, r = 0, len(height) - 1 # 左右兩個指針捐腿，從兩頭往中間移動
ans = 0 # 記錄面積
while l < r:
area = min(height[l], height[r]) * (r - l)
# 比較記錄最大的面積
ans = max(ans, area)
# 如果左邊的值比右邊的小就移動左邊的指針
if height[l] < height[r]:
l += 1
# 反之纵朋，如果右邊的值不比左邊的大，就移動右邊的指針
else:
r -= 1
return ans
復(fù)雜度分析
- 時間復(fù)雜度：O(N)茄袖，雙指針總計最多遍歷整個數(shù)組一次操软。
- 空間復(fù)雜度：O(1)，只需要額外的常數(shù)級別的空間宪祥。
