leetcode 第11题（container with most water）基于python实现

此题的编程并不困难，可以说十分简单，只有寥寥几行，但难处在于思想。

题目要求要实现装水的最大。但用双重循环提交时，会出现超时。

得改变思路，只能用单重循环。

用一个例子，假设输入的值为

5,3,6,2,7,8,1,6

数字在坐标上的值如上图所示，一开始设计两个值left，right分别指向数组的开始与结束处。用一个中间变量记录所装的水的最大值。比较left与right所指向的值的大小，对于所指的小的值丢弃，水的量与中间变量max所存的值做比较，若是大于max的值则替换，指针向中间移一位。

例如在上图开始时，指针left所值向的值小于right所指向的值，则丢弃left中所指向的值，left加1。如下图：

那么为什么可以丢弃掉1处的值呢？

因为数组1的值的作用是与其他处的值相匹配，而在上面，数组1的值与其他值匹配所装的最大的水是与数组8的匹配，所以只需将数组1与数组8匹配的这个最大值记录就可以了。

接下来的步骤完全是重复上面的步骤，当全部的值丢弃以后，所记录的值便为全局的最大值。

基于python的源码：

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