[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.

Note: You may not slant the container.

思路：

1.由题意所知，题目实际是在二维坐标的第一象限给了一组坐标点(x1,y1),(x2,y2),```,(xn,yn)，题目欲求两点xi,xj(j>i)，使得(xj-xi)*min(yi,yj)在所有组合中最大；

2.观察第一象限的所有点会发现，若xk>xi，那么只有yk>yi，才有可能使得(xj-xk)*min(yk,yj)>(xj-xi)*min(yi,yj)，同理，若xl<xj，只有yl>xj时，才有可能使得(xl-xi)*min(yi,yl)>(xj-xi)*min(yi,yj)；（其实也就是说若从两边向中间挤压，要想保持容积不变或者使得容积增加，那么y方向的值必须增加）；

3.算法的主要思路基于2，从头和尾向中间遍历数组，其实算法还可以简化为如果前指针所指数据小于后指针所指数据，那么前指针后移（不断寻找更高的点），反之，则后指针前移。

代码：

class Solution{
public:
	int maxArea(vector<int> &height){
		int front=0;
		int back=height.size()-1;
		int result=0;
		while(front < back)
		{
			int tmp=(back-front)*min(height[front],height[back]);
			result=result>tmp?result:tmp;
			if(height[front]<height[back])
				++front;
			else
				--back;
		}
		return result;
	}
};