Container With Most Water (最大盛水量)leetcode11-蒲公英云

Container With Most Water (最大盛水量)leetcode11

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 and n is at least 2.

给定一个数组每个数代表一块木板的高度横坐标x的宽度代表木桶的宽度，求最大容积（木桶的高只能为两块木板的最低的那一个）

code1：暴力破解，所有结果求出来取最大值（超时）

public int maxArea(int[] height) {
        /*int max=Integer.MIN_VALUE;
        for(int i=0;i<height.length;i++){
            for(int j=i+1;j<height.length;j++){
                int h=height[i]>height[j]?height[j]:height[i];
                if(h*(j-i)>max)
                    max=h*(j-i);
            }
        }
        return max;
}

code2：假设第1块木板和最后一块组成的容积最大，如果还有更大的，那么小的木板往中心移，知道左边的木板位置等于右边模板的位置

20180518235931436

code：

public int maxArea(int[] height) {
        int max=Integer.MIN_VALUE;
        for(int i=0,j=height.length-1;i<j;){
            if(height[i]>height[j]){
                max=Math.max(max,height[j]*(j-i));
                j--;
        }else{
                max=Math.max(max,height[i]*(j-i));
                i++;
        }
        }
        return max;
    }