Container With Most Water

思路一 使用空间换时间，使用空间记录所有高度得最左坐标，左右各计算一次，即可得出结论，O(max(height) + len(height))，M(max(height) + len(height))

class Solution:
    def cal(self, height):
        left = [-1] * (max(height) + 10)
        area = 0
        for (i, v) in enumerate(height):
            if left[v] == -1:
                left[v] = i
                k = v - 1
                while k >= 0 and left[k] == -1:
                    left[k] = i
                    k -= 1 
            else:
                area = max(area, (i - left[v]) * v)
        return area

    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # height max is 1000
        area = max(self.cal(height), self.cal(height[::-1]))
        print(area)
        return area        

思路二 左右递减计算

class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        area = 0

        left = 0
        right = len(height) - 1

        while left < right:
            area = max(area, min(height[left], height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        print(area)
        return area