11. Container With Most Water

題目

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

題目連結

此題需要從代表高度的陣列當中挑出兩根柱子，使其中間圍出的面積為最大值。

思路

根據題目的計算方式，除了高度會影響面積之外兩根柱子之間的距離也會影響，因此在想法上會從最外圍的兩邊開始往內找，因為從最外圍的兩邊作為起點的話它的寬必定是最大值。接下來找出兩邊比較短的那邊開始向內縮，將面積計算出來之後和當前的最大值進行比較，直到左右兩邊碰在一起的時候就代表結束搜尋。

流程上大概是：

loop:
  計算面積 -> 和當前最大值比較 -> 左右取短邊往內移動

Full Code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        mxArea = 0
        left = 0
        right = len(height) - 1
        while left != right:
            left_height = height[left]
            right_height = height[right]
            area = (right - left) * min(left_height, right_height)
            mxArea = max(mxArea, area)
            if left_height <= right_height:
                left += 1
            else:
                right -= 1

        return mxArea