題目鏈接
難度：中等 ??????類型： 數(shù)組、雙指針
給定 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)成的容器可以容納最多的水。
示例
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
解題思路
這種方法背后的思路在于，兩線段之間形成的區(qū)域總是會(huì)受到其中較短那條長(zhǎng)度的限制。此外，兩線段距離越遠(yuǎn)，得到的面積就越大。
我們?cè)谟删€段長(zhǎng)度構(gòu)成的數(shù)組中使用兩個(gè)指針，一個(gè)放在開始，一個(gè)置于末尾。 此外，我們會(huì)使用變量 maxarea 來持續(xù)存儲(chǔ)到目前為止所獲得的最大面積。 在每一步中，我們會(huì)找出指針?biāo)赶虻膬蓷l線段形成的區(qū)域，更新 maxarea，并將指向較短線段的指針向較長(zhǎng)線段那端移動(dòng)一步。
代碼實(shí)現(xiàn)
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
start = 0
end = len(height)-1
max_val = 0
while start<end:
max_val = max(max_val, (end-start)*min(height[start], height[end]))
if height[start]>height[end]:
end -= 1
else:
start += 1
return max_val
