LeetCode算法11：java 盛水最多的容器

题目
给定 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
思路
可能有同学会采用循环暴力求解，但是这不是本题要的思路。这里道题用了一个代码上非常简单的解法。但是对于其算法正确性的证明，却是比较复杂。这里先给出代码及说明。之后再给出算法的证明。
代码

public class _11ContainerWithMostWater{
	
	public int maxArea(int[] height){
		
		int i = 0;
		int j = height.length-1;
		int area = 0;
		int areaNow = 0;
		
		while(i!=j){
			areaNow = Math.min(height[i],height[j])*(j-i);
			area = Math.max(area,areaNow);
			if(height[i]<=height[j]){
				i++;
				}else{
				j--;
					}	
			}
		return area;
		}

	public static void main(String[] arg){
_11ContainerWithMostWater ContainerWithMostWater =
	 new _11ContainerWithMostWater();
		
		int[] height = {1,8,6,2,5,4,8,3,7};
		int area = ContainerWithMostWater.maxArea(height);
		System.out.println(area);	
		}
}

解题思路是由两侧向中间逼近，每次移动的坐标是高度值较小的那个。统计移动过程中的最大值。

证明