Leetcode 11

此题是一道非常经典的算法题。给定一系列高度的横线，算其所能围成的盛水容器的面积最大多少。可以直观地发现整个盛水面积是与两个横线之间的距离以及他们的最小高度决定的。

一个非常直观的想法是遍历两两线段，取最大的面积，但是这样做很明显是超时的，所以一定有更加简单的方法来处理，也就是有一些情况是不需要考虑的。由于暴力遍历的时间复杂度是O(n^2)，由于二分的方式并不明显，所以考虑O(n)复杂度的算法。

具体过程是，在数组的开始和结果各建立一个索引，然后逐渐向中间移动。移动的规则如下: 看目前左右两边的线段哪个更短，如果是左边更短，则让左边的index向右移动。如果是右边的更短，则相反。这样做的依据是，我们考虑相反的情况，如果是在长的那边移动的话，当移动到的那条线段比另一边的线段长时，由于另一边的线段是短的，所以整个面积取决于另一边的线段，然而距离却更加接近了，所以肯定比之前的要小。当移动到的那条线段要短时，则面积会更加的小。所以在长的那边进行移动的结果是无论如何都会变小，而我们想要的是最大的，则否定这种操作的发生。相反，如果我们是在短的那边移动，则有可能出现距离变短，但两个线段最小的那个更长，从而导致面积更大。

在处理该题时，一开始想到要这样移动，即从两边向中间靠拢，但是没有想到具体的移动方式，这是因为可能之前做过类似的题目有印象，但是没有深入地理解和巩固，只剩下大概的印象，对题目的理解停留在表面，需要多练习巩固~

代码如下：

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