1.题目描述
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.
给定n个非负整数a1 a2，。a，每个代表一个坐标点(i，ai)。n垂直的线是这样画的，直线i的两个端点在(i，ai)和(i，0)中，找到两条直线，和x轴形成一个容器，这样容器就包含了最多的水。
2.题目分析
明明是要求面积，竟然说是要求容积，然后一开始就在考虑底面积怎么求。言归正传，如果采用暴力搜索法，遍历每一对组合，相对来讲复杂度实在是太高了，为O(n*n)。采用线性时间算法，双指针分别从首尾进行遍历，和求TwoSum，TreeSum方法一样。
3.解题思路
class Solution(object): def maxArea(self, height): """ :type height: List[int] :rtype: int """ maxarea=0 #最大面积 left=0 #左指针 tmax=0 #最大高度 right=len(height)-1 #右指针 while left<right: h=min(height[left],height[right]) #高度 tmax=max(tmax,h) #最大高度 maxarea=max((right-left)*h,maxarea) #求最大面积 while left<right and height[left]<=tmax: left+=1 #如果左指针指的高度小于最大高度，左指针跳过一位 while left<right and height[right]<=tmax: right-=1 #右指针同上 return maxarea #返回最大面积