LeetCode 11. Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

这道求装最多水的容器的题和那道 Trapping Rain Water 很类似，但又有些不同，那道题让求整个能收集雨水的量，这道只是让求最大的一个的装水量，而且还有一点不同的是，那道题容器边缘不能算在里面，而这道题却可以算，相比较来说还是这道题容易一些，存雨量计算其实就是min(h[l], h[r])*(r-l), 最短的墙的高度乘以两堵墙间的距离，所以这里需要定义l和r两个指针分别指向数组的左右两端（从两堵墙最大距离开始计算，所以是首位指针），然后两个指针向中间搜索，每移动一次算一个值和结果比较取较大的，容器装水量的算法是找出左右两个边缘中较小的那个乘以两边缘的距离。Time complexity: O(n)，Space complexity: O(1)

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