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.

基本思路：

首先，我们假设找到了最大的容积S，即由ai，aj和x轴围成，那么我们想一下，此时如果i的左边有比ai大的数，那么此时最大面积就不可能是S了（因为x轴的长度增加了，而高度最少是保证很原来相等的，当增加的是较长的边不影响高度，这是由短板理论决定的。），同理，j的右边也是如此。此时，我们得出了一个结论，当出现最大面积时，i的左边和j的右边的高度都比ai和aj小。

那么，现在考虑i和j的中间，当中间有比ai和aj大的数时，有可能出现比S更大的容积，因为尽管x轴减小了，当高度补齐了它的不足。所以，我们从两头向中间靠拢，同时更新候选值；在收缩区间的时候优先从  x, y中较小的边开始收缩（这点很重要，若是从较大的开始收缩会越来越小）。

	public int min(int i,int j)
	{
		return i<j?i:j;
	}
	public int maxArea(int[] height)
	{
		if(height==null||height.length==0)
			return 0;
		int area = 0;
		int maxArea = 0;
		
		for(int i = 0,j=height.length-1;i<j;)
		{
			area = min(height[i],height[j])*(j-i);
			maxArea = maxArea>area?maxArea:area;
			
			if(height[i]<height[j])
			{
				int tmpi = i;
				while(tmpi<j&&height[tmpi]<=height[i])
				{
					tmpi++;
				}
				i = tmpi;
			}
			else
			{
				int tmpj = j;
				while(tmpj>i&&height[tmpj]<=height[j])
				{
					tmpj--;
				}
				j = tmpj;
			}
		}
		
		return maxArea;
	}

Container With Most Water,布布扣,bubuko.com

Container With Most Water

原文：http://blog.csdn.net/cow__sky/article/details/21324777