算法：盛最多水的容器--LeetCode

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

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

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

示例:

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

解題思路：面積=底*高，底最大為數組長度，故採用兩端向中間漸進方式計算最大面積，每次高度小的一端移動。

python：

<code>class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max = 0
        left, right = 0, len(height) - 1
        while left < right:
            if height[right] > height[left]:
                s = (right - left) * height[left]
                left += 1
            else:
                s = (right - left) * height[right]
                right -= 1
            if s > max:
                max = s
        return max/<code>

執行用時 :44 ms, 在所有 Python 提交中擊敗了100.00%的用戶

內存消耗 :12.5 MB, 在所有 Python 提交中擊敗了44.84%的用戶

go：

<code>func maxArea(height []int) int {
    ret := 0
    left, right := 0, len(height)-1
    for left < right {
        s := 0
        if height[left] > height[right] {
            s = (right - left) * height[right]
            right--
        } else {
            s = (right - left) * height[left]
            left++
        }
        if s > ret {
            ret = s
        }
    }
    return ret
}/<code>

執行用時 :12 ms, 在所有 Go 提交中擊敗了96.22%的用戶

內存消耗 :5.8 MB, 在所有 Go 提交中擊敗了53.51%的用戶

閱讀更多 程序猿阿木 的文章

關鍵字: Python 鏡音雙子 人工智能