给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
- 示例:
输入: [1,8,6,2,5,4,8,3,7] 输出: 49
笨方法
既不是单纯的找宽度最宽的两点，也不是找高度最高的两点，而是要找高*宽最大的参数。暴力搜索肯定是一种解决方案，但绝不是效率最高的方式。最好是能够线性搜索。
能否用递归的思想解决，或者用二分法解决？递归看起来不怎么靠谱，因为局部能够容纳的最多水量与总体水量没有必然关系。二分法似乎也不行，如果所有的矮柱子都分布在左边，所有的高柱子都分布在右边，而高柱子又远远高于矮柱子，这时最大容水量的矩形应该在右侧。
先用暴力搜索来处理吧，处理过程中应当注意：index和value都需要用到。考虑到两两柱子的匹配存在重复，应可减少一半的比对时间。
代码倒是挺简单的，但是执行效率肯定不高。时间复杂度O(n^2)，果然超时了。
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
area=0
for i,c in enumerate(height):
for i1,c1 in enumerate(height):
if i1>i and (i1-i)*min(c,c1)>area:
area=(i1-i)*min(c,c1)
return area
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
area=0
l=len(height)
for i,c in enumerate(height):
for j in range(i+1,l,1):
area=max(area,(j-i)*min(c,height[j]))
return area
聪明方法
采用官方题解中的双指针法，其基本原理是：左右两端各一个指针，如果其中一端的长度小于另一端的长度，则移动较短的那一端。因为容器的容量受较短的那个线段影响，而不会受较长的线段影响。每次移动都记录当前的最大面积。
相对于笨方法，此方法的核心提升点在于：用了双指针。移动指针的时候，可以比较两个线段的长度后，再决定移动哪一个。
向内移动较长的线段时，由于宽度减少了，最短线段的长度不可能增加，因此总面积必然减少。所以，只需要向内移动较短的线段就行了，尽管宽度也减少了，但最短线段的长度可能会增加，从而导致总面积可能增加。
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
area=0
l,r=0,len(height)-1
while l<r:
area=max(area,(r-l)*min(height[l],height[r]))
if height[l]<height[r]:
l+=1
else:
r-=1
return area
