Question：

<b>    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.
</b>
<b>tags:</b>It's not a real tough question.But the test data set is very large.So you can't just use loop with O(n^2) to solve.The O(n^2) solution will result in Time Limit Exceeded.So I need to figure out an O(n) or O(nlogn) to solve.

Solution 1:

<b>DEC:</b>the 4ms solution in LeetCode

 public int maxArea(int[] height) {
   int maxRes = Integer.MIN_VALUE;
    int len = height.length;
    int maxHeight;
    int tmpRes;
    boolean bLeft = true;
    int leftPointer =0,rightPointer = len-1;
    while(leftPointer<rightPointer){
        // 判断是否是左点的height值更大
        if (height[leftPointer]<height[rightPointer]) {
            bLeft=false;
            maxHeight =  height[leftPointer];
        }else {
            bLeft = true;
            maxHeight = height[rightPointer];
        }
        // 值比最大值大，则修改最大值
        tmpRes = maxHeight*(rightPointer-leftPointer);
        if (tmpRes>maxRes) {
            maxRes = tmpRes;
        }
        //如果左边更大，则右指针向左移动
        if (bLeft) {
            rightPointer--;
        }else {
            leftPointer++;
        }
    }
    return maxRes;
}

    As you can see,the code is too long and complex.
Solution 2:

<b>DEC:</b>the modified 5ms solution in LeetCode

 public int maxArea(int[] height) {
    int maxRes = Integer.MIN_VALUE;
    int len = height.length;
    int maxHeight;
    int tmpRes;
    int leftPointer =0,rightPointer = len-1;
    int lastleft=0,lastright=0;
    while(leftPointer<rightPointer){
        // 判断是否是左点的height值更大
        lastleft = leftPointer;
        lastright = rightPointer;
        if (height[leftPointer]<height[rightPointer]) {
            
            maxHeight =  height[leftPointer++];
            
        }else {
            
            maxHeight = height[rightPointer--];
        }
        // 值比最大值大，则修改最大值
        tmpRes = maxHeight*(lastright-lastleft);
        maxRes = Math.max(tmpRes, maxRes);
    }
    return maxRes;
}

    You can see that the code is clean but slower than the solution 1.What a fuck!It worked badly.Why doest it happen?
    The algorithm is used for searching for the biggest container to store water.So the short one is the decisive factor according to barrel theory.Besides,the most time consuming operation is the assignment.In the new algorithm the consuming operation is more than the old one (Math.max).So i get a better algorithm below.
Solution 3:

DEC: 3ms solution in LeetCode

public int maxArea(int[] height) {
  int maxRes = Integer.MIN_VALUE;
    int maxHeight;
    int tmpRes;
    int leftPointer =0,rightPointer = height.length-1;
    while(leftPointer<rightPointer){
        tmpRes = rightPointer-leftPointer;
        // judge if the left pointer's height bigger?
        if (height[leftPointer]<height[rightPointer]) {
            maxHeight =  height[leftPointer++];
        }else {
            maxHeight = height[rightPointer--];
        }
        // to get the result of result now
        tmpRes = maxHeight*tmpRes;
        // get the max result
        if (tmpRes>maxRes) {
            maxRes = tmpRes;
        }
    }
    return maxRes;

}
Conclusion:

    The good algorithm is good in decisive part.It's just like the amdahl's law。