LeetCode Container With Most Water

LeetCode解題之Container With Most Water

原題

給定一組長短不一的隔板，挑其中的兩塊板，使得板子之間能裝最多的水。

注意點：

例子：

輸入: height=[1,1,1]
輸出: 2

解題思路

我們把兩塊板分為左板、右板，現在考慮如下情況。假設左板高度為h，且比右板低，兩塊板之間的距離為w，則此時最多能裝水w*h，此時我們嘗試移動隔板。如果將左板向右移，那麼有可能使容積變大，例如，左板右邊的板子高h1（還是比右板低），此時最多裝水(w-1)*h1，有可能比w*h大；如果將右板向左移，由於水的高度不能高於左板，所以容積最多為(w-1)*h，肯定比w*h小。基於上面的假設，我們只要把兩塊隔板依次向中間靠攏，就可以求出最大的容積。

AC源碼

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

if __name__ == "__main__":
    assert Solution().maxArea([1, 1]) == 1