題目：給定 n 個(gè)非負(fù)整數(shù) a1醉拓，a2伟姐，...，an亿卤，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, ai) 愤兵。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個(gè)端點(diǎn)分別為 (i, ai) 和 (i, 0)排吴。找出其中的兩條線秆乳，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器钻哩，且 n 的值至少為 2
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]屹堰。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49街氢。
示例:
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
雙指針法
思路在于扯键，兩線段之間的面積總是受制于較短的那條。此外珊肃，兩線段距離越遠(yuǎn)荣刑，得到的面積就越大。
使用兩個(gè)指針伦乔，一個(gè)放在開始厉亏，一個(gè)置于末尾。
選擇較短的一根向內(nèi)移動(dòng)一步烈和，直至兩指針相遇爱只。其中每次移動(dòng)時(shí)計(jì)算面積，并保留最大面積斥杜。
對(duì)于每一步的狀態(tài)虱颗，其面積受制于較短指針。考慮指針向內(nèi)移動(dòng)高帖，若較長(zhǎng)指針向內(nèi)移動(dòng)，并不會(huì)帶來(lái)面積的增加乖阵，只會(huì)導(dǎo)致面積減小。因此瞪浸，只有移動(dòng)較短指針才可能出現(xiàn)面積變大的情況。
故在指針向內(nèi)移動(dòng)的過程中钩蚊，必然會(huì)得到面積最大值蹈矮。該方法的時(shí)間復(fù)雜度為
class Solution:
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
area = 0
i, j = 0, len(height)-1
while i < j:
area = max(area, (j-i)*min(height[i], height[j]))
if height[i] <= height[j]:
i += 1
else:
j -= 1
return area
