Container With Most Water ！！！！！！！！！！

Q:
Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i).
n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.
A:

----------------------------------第三遍-----------------

上面都是O(n^2)的复杂度，但是，有个O(n)的复杂度的。

下面是分析 （引用）

First of all, to understand the problem. What it asks is, to find the maximum value of (i-j)*min( a_i , aj  ). At the first , I only think of brute force solution which will cost O(n^2). Then I found a solution with linear cost. 

Set two pointers, point to begin and end. Move the pointer which points to the smaller element in array. The algorithm is simple, the hardest part is to prove the correctness of this algorithm. 

Proof:
 Because the contain volume is decided by the shorter line between two.
Since a_i is lower than aj,  so there will be no jj < j that make the area from i, jj is greater than area from i,j so the maximum area that can benefit from i is already recorded.

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

思路： 就是 一个个往上加line。  *****************但是这样会超时＊＊＊＊＊＊＊

public class Solution {
   public int maxArea(int[] height) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int maxWater = 0;
        int n = height.length ;
        if(n<=1 ) {
            return maxWater;
        }
        for(int i =1;i< n ;i++){
            int maxEndHere = maxEndAtI(height,i,maxWater);
            maxWater = maxWater>maxEndHere?maxWater:maxEndHere;
        }
        return maxWater;
    }
    private int maxEndAtI(int[] height, int i, int maxWater){
        // return the max water that returns at current position
        if( height[i] * i  < maxWater||  height[i] == 0 ){  // height[i] is too low to exceed former maxWater
            return 0;
        }
        //start from the possible left position
        int leastLength = maxWater/height[i];
        int leftLineMostRighPos = i - leastLength;
        int curMaxWater = maxWater;
        for(int j= leftLineMostRighPos; j>=0;j--){
            int curWater = Math.min(height[j],height[i])*(i-j);
            if(curMaxWater < curWater){
                curMaxWater = curWater;
            }
        }
        return curMaxWater;
    }
}

Mistakes:
1:又一次出现了，除零的问题。。 ╮(╯▽╰)╭

-------------------第二遍----------
1： 题意理解错误， 应该是 2条line，  而不是bar，  因此，即使输入是【1,1】的时候， 也可以盛1单位的水。
2： 题意理解错误，  两条line，中间即使是有个比他们都高的， 也不碍事。
例如，输入是：[1,2,1] 的时候，输出应该是2、

3:   哎， again，  出现了除零的问题。   ----------Tiger， 记住，只要是出现除数， 就要检查其值是否为0.


Learned:
1: 即使是int类型的变量， 如果要 调用的话，也需要事先initialize。