題目

給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線(xiàn)，第 i 條線(xiàn)的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。找出其中的兩條線(xiàn)，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。返回容器可以?xún)?chǔ)存的最大水量。
說(shuō)明：你不能傾斜容器。

例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋?zhuān)簣D中垂直線(xiàn)代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。

方法一：暴力解法

計(jì)算所有可能的面積取最大值

class Solution(object):
    def maxArea(self, height):
        sum = 0
        for i in range(len(height)-1):
            for j in range(i, len(height)):
                sum = max(sum, (j-i)*min(height[i], height[j]))
        return sum

※ 超出時(shí)間限制

方法二：雙指針

• left 指向數(shù)組 height 首部，right 指向數(shù)組 height 尾部
• sum 記錄最大面積
• 循環(huán)直至左右指針相遇
  • 若左指針指向的數(shù)字小于右指針指向的數(shù)字，即左邊線(xiàn)比右邊線(xiàn)短，那么更新此時(shí)的最大面積，并將指向較短線(xiàn)的指針向內(nèi)移動(dòng)一步，在此處便是左指針
  • 若右指針指向的數(shù)字大于左指針指向的數(shù)字，即右邊線(xiàn)比左邊線(xiàn)短，那么更新此時(shí)的最大面積，并將指向較短線(xiàn)的指針向內(nèi)移動(dòng)一步，在此處便是右指針
    ※ 無(wú)論什么狀況下，只要指針向中間移動(dòng)，那么 x 軸的邊一定會(huì)變短。
    ※ 若將指向兩板之中較短板的指針向內(nèi)移動(dòng)一步，此時(shí)的 min(height[left], height[right]) 可能變大可能變小也可能不變，那么面積可能變大可能變小也可能不變；但是若將指向兩板之中較長(zhǎng)的指針向內(nèi)移動(dòng)一步，此時(shí)的 min(height[left], height[right]) 只可能變小或不變，那么面積一定變小。所以，只有不斷嘗試將指向較短邊的指針向內(nèi)移動(dòng)，才可能得到較大的面積

class Solution(object):
    def maxArea(self, height):
        left, right = 0, len(height)-1
        sum = 0
        while left < right:
            if height[left] < height[right]:
                sum = max(sum, height[left]*(right-left))
                left += 1
            else:
                sum = max(sum, height[right]*(right-left))
                right -= 1
        return sum

參考

代碼相關(guān)：https://leetcode.cn/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/