LeetCode OJ 之 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.
思路：最直观的解法：

public class Solution {
    public int maxArea(int[] height){
        int len = height.length;
        int result = 0;
        for(int i = 0; i < len; i++){
            for(int j = i+1; j < len; j++){
                int tempresult = 0;
                if(height[i] < height[j]){
                    tempresult = height[i] * (j-i);
                }
                else{
                    tempresult = height[j] * (j-i);
                }
                if(tempresult > result){
                    result = tempresult;
                }
            }
        }
        return result;
    }
}

此算法的时间复杂度为O(n2)，因此不会被OJ判定为通过。我们可以思考，对于该数组中的一个数m，以他为一条边的桶容积最大时应该满足什么条件，容易想到，只需要找到距离该数最远的一个大于该数的数组中的数n，n和m所组成的桶即为容积最大的桶。根据这种思路，可以从数组的第一个元素开始，从数组末尾开始寻找第一个大于该元素的元素。但是，有可能大于该元素的数全部位于该元素之前，例如当数组为倒序排列时。考虑倒序数组这一情况，此时我们的思路仍然是正确的，只是此时我们的遍历顺序应该从数组的末尾开始。应此，一个通用的解法可能是，从数组的开始与结尾同时开始遍历，依次找到每一个元素所能组成的最大容积的桶。那么可以写出程序：

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