題目

給定 n 個非負整數(shù) a1，a2，...，an，每個數(shù)代表坐標中的一個點 (i, ai) 。在坐標內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

說明：你不能傾斜容器，且 n 的值至少為 2。

最大容器

圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。

示例

輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49

解答

方案1：暴力求解

我們考慮所有的容器組合，用兩個指針——左指針（left）和右指針（right）標記容器兩壁的位置，計算每個容器所對應的容積并更新最大值。

class Solution:
    def maxArea(self, height):
        max_area = 0
        for right in range(1, len(height)):
            for left in range(right):
                cur_area = min(height[left], height[right]) * (right - left)
                max_area = max(max_area, cur_area)

        return max_area

方案2：向中靠攏

容器的容積與底面積（這里我們把兩個板之間的距離稱為底面積）有關，而且在底面積固定的情況下，短板效應決定了容器的容積取決于長度較低的板。

我們定義左右兩個指針，左指針（left）和右指針（right）的初始位置在數(shù)組（height）兩端的位置，此時相當于容器的底面積最大，然后比較兩指針對應的板的高度，高度較低的指針向另一個指針方向移動一個單位距離，記錄下每次的最大容積，直到兩者相遇為止。

這里的邏輯是，左指針右移一個單位或者右指針左移一個單位后，兩個指針的距離是一樣的，相當于容器的底面積是一樣的，在這樣的情況下我們就要考慮如何能保證移動指針后的短板盡可能最長，兩指針向中間移動相當于換掉一個板，如果去除短板保留長板相比于去除長板保留短板，更有可能使容器的面積增大。

以上是直觀理解，需要嚴格數(shù)學推導。。。

class Solution:
    def maxArea(self, height):

        left, right, max_area = 0, len(height)-1, 0     # 從兩端開始，左右指針向中間走

        while left < right:

            current_area = min(height[left], height[right]) * (right-left)
            max_area = max(max_area, current_area)
            if height[left] > height[right]:
                right -= 1
            else:
                left += 1
        return max_area

如有疑問或建議，歡迎評論區(qū)留言~