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

约定不等于承诺〃 2022-05-24 02:57 154阅读 0赞

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;
        }

[20180518235931436]: /images/20220524/6aa89b52c68b4896a86d2c06225da59d.png