首页 > 试题广场 >

盛水最多的容器

[编程题]盛水最多的容器

热度指数：33193 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水

1.你不能倾斜容器

2.当n小于2时，视为不能形成容器，请返回0

3.数据保证能容纳最多的水不会超过整形范围，即不会超过2³¹-1

数据范围:

$0<=height.length<=10^5$

$0<=height[i]<=10^4$

如输入的height为[1,7,3,2,4,5,8,2,7]，那么如下图:

示例1

输入

[1,7,3,2,4,5,8,2,7]

输出

示例2

输入

[2,2]

输出

示例3

输入

[5,4,3,2,1,5]

输出

算法知识视频讲解

Java

做则必成的勇气和信心

public int maxArea (int[] height) {
        //面积，底*高，面积取决于短柱子
        //较短边长*底部距离，(j-i)已经拉到最长，所以能改变的只有height[短]，舍弃较短的边
        if(height.length<2) return 0;
        int ans=0;
        int left=0;
        int right=height.length-1;
        while(left<right){
            int areas=Math.min(height[left],height[right])*(right-left);
            ans=Math.max(ans,areas);
            if(height[left]<height[right]) left++;
            else right--; 
        }
        return ans;
    }

发表于 2023-07-23 15:13:48 回复(0)

Java

BlueProtocol

暴力破解超时，采用比较最大长度法进行解决

public class Solution {

    public int maxArea1 (int[] height) {
        // write code here
        int length = height.length;
        if (length < 2) return 0;
        int max = 0;
        int left = 0;
        int right = length - 1;
        while (left < right) {
            max = Math.max(max, Math.min(height[left], height[right]) * (right - left)) ;
            if (height[left] < height[right]) left++;
            else right--;
        }
        return max;
    }
    
    
            // for(int i = 0;i <length ;i++) {
        //     for (int j = i + 1;j < length ;j++) {
        //          if (height[i] >= height[j]) {
        //             max = Math.max(max,(j-i)*height[j]);
        //          }else{
        //              max = Math.max(max,(j-i)*height[i]);
        //          }
        //     }
        // }
}

发表于 2023-03-21 18:15:09 回复(0)

Java

小牛749

 public int maxArea (int[] height) {
        if(height.length<2){
            return 0;
        }
        int i = 0,j = height.length-1; //初始化双指针，一个指头，一个指尾
        int area = 0; //初始化面积
        while(i<j){
            int temp = height[i]>height[j]?height[j]*(j-i):height[i]*(j-i);     //计算每一次的面积
            area = area>temp?area:temp; //area每次取大的面积
            if(height[i]>height[j]){     //短板移动，谁短谁动
                j--;
            }else{i++;}
        }
        return area;
    }

发表于 2023-03-07 17:48:11 回复(0)

Java

wpcAlex

import java.util.*;


public class Solution {
    public int maxArea (int[] height) {
        // write code here
        int ans = 0;
        int l = 0, r = height.length - 1;
        while (l < r) {
            ans = Math.max(ans, Math.min(height[l],height[r]) * (r - l));//计算盛水选择短板
            if (height[l] < height[r])  ++l;
            else --r; //移动短板
        }
        return ans;
    }
}

发表于 2023-01-28 14:25:18 回复(0)

Java

ludvig

//1.双指针 i j 分别从数组的两端开始夹

//2.木桶的短板原则，总是最短的边决定桶的容积，并且容积=更短边*(j-i)

//3.让更短的边往里走一走，看看能不能冒着缩短j-i的风险搏得一个更大的短边使得整体容积更大

//4.可以稍微优化一下，再缩进更短边的时候，比原来边短的边统统过掉了，直接指向到比原来最短边长的边，

因为只有短边边长整体容积才有可能更大，否则边长变短，横距离还变短，整体容积不可能变得更大.

import java.util.ArrayList;

public class Solution {

public int maxArea (ArrayList<Integer> height) {

int maxVessel = 0;

int i = 0;

int j = height.size() - 1;

while (i < j) {

int min = Math.min(height.get(i), height.get(j));

if ((min * (j - i)) > maxVessel) {

maxVessel = min * (j - i);

}

if (height.get(i) < height.get(j)) {

while (i < j && height.get(i) > height.get(i + 1)) {

i++;

}

i++;

} else {

while (j > i && height.get(j) > height.get(j - 1)) {

j--;

}

j--;

}

return maxVessel;

}

发表于 2022-09-28 12:33:13 回复(0)

Java

程序员大鹏

public int maxArea (int[] height) {
        // write code here
        
        
        int leftIndex = 0;
        int rightIndex = height.length-1;
        int maxArea = 0;
        
        while(leftIndex<rightIndex) {
            int leftHeight = height[leftIndex];
            int rightHeight = height[rightIndex];
            
            int currentArea = 0;
            if(leftHeight <= rightHeight) {
                currentArea = leftHeight * (rightIndex-leftIndex);
                leftIndex ++;
            } else {
                currentArea = rightHeight * (rightIndex-leftIndex);
                rightIndex --;
            }
            
            if(currentArea > maxArea) {
                maxArea = currentArea;
            }
        }
        
        return maxArea;
    }

发表于 2022-09-08 23:52:40 回复(1)

Java

yxjing

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] height) {
        // write code here
        //特殊情况
        if(height.length==0||height.length==1){return 0;}
        //一般情况
        int left=0,right=height.length-1;
        int max=Integer.MIN_VALUE;
        while(left<right){
            int V=(right-left)*Math.min(height[left],height[right]);
            max=V>max?V:max;
            if(Math.min(height[left],height[right])==height[left]){
                left++;
            }else{
                right--;
            }
        }
        return max;
    }
}

发表于 2022-08-18 19:14:59 回复(0)

Java

牛客292107984号

证明：为什么移动长边不可能增大容器？

1. 移动会造成低边变小；

2. 受限于短边，移动后最短边只能是小于或等于原来的短边；

3. 所以移动长边之后容器只会缩小。

使用数学符号：

原来面积 b * min{l, r}

移动长边（假设为 r ）之后有

b' < b

min{l', r'} = min{l, r'} <= min{l, r}

所以移动长边之后的面积 area' = b' * min{l', r'} < area = b * min{l, r}。

发表于 2022-08-17 17:11:32 回复(2)

Java

lizi-hust

import java.util.*;
public class Solution {
    public int maxArea (int[] height) {
        int n = height.length;
        int res = 0;
        int left = 0, right = n-1;
        while(left < right){
            res = Math.max(res, (right - left) * Math.min(height[left], height[right]));
            if(height[left] < height[right]) left++;
            else right--;
        }
        return res;
    }
}

发表于 2022-08-07 16:29:40 回复(0)

Java

牛客214201518号

public int maxArea (int[] height) {
// write code here
int max = 0;
int left = 0; int right = height.length - 1;

while(left < right){
if(height[left] <= height[right]){
max = Math.max(height[left++] * (right - left + 1), max);
}else{
max = Math.max(height[right--] * (right - left + 1), max);
}

}

return max;
}

发表于 2022-07-29 23:14:19 回复(0)

Java

FARO_Z

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

发表于 2022-07-22 01:06:51 回复(0)

Java

pickpig

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param height int整型一维数组
* @return int整型
*/
public int maxArea (int[] height) {
// write code here
if(height.length < 2) {
return 0;
}
int ret = 0;
int left = 0;
int right = height.length - 1;
while(left < right) {
//高
int h = Math.min(height[left],height[right]);
//宽
int b = right - left;
if(b < 0) {
b = -b;
}
ret = Math.max(ret,h * b);
if(height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ret;
}
}

发表于 2022-05-29 20:31:09 回复(0)

Java

牛客112285422号

//双指针
    //对于遍历到的l，r先判断形成的容器大小，和max比较，容器大小的高度，由较小的高度决定
    //因为无论是l动还是r动，都会让宽变小，此时要找的是最大容器值
    //所以要让高度尽量高，因为现在的瓶颈在较低的边上，所以较低的边所在的位置移动
    public int maxArea (int[] height) {
        // write code here
        if(height==null||height.length<2)
            return 0;
        int l=0;
        int r= height.length-1;
        int max=Integer.MIN_VALUE;
        while (l<r){
            int index= height[l]<= height[r]?l:r;
            max=Math.max(max,(r-l)* height[index]);
            if (index==l)
                l++;
            else 
                r--;
        }
        return max;
    }

发表于 2022-05-18 15:53:32 回复(0)

Java

世界杯2009

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param height int整型一维数组
     * @return int整型
     */
    public int maxArea(int[] height) {
        if (height == null || height.length == 0 || height.length == 1) {
            return 0;
        }
        // write code here
        int max = Integer.MIN_VALUE;

        int start = 0;
        int end = height.length - 1;
        while (start < end) {
            if (height[start] < height[end]) {
                max = Math.max((end - start) * height[start], max);
                start++;
            } else {
                max = Math.max((end - start) * height[end], max);
                end--;
            }

        }
        return max;
    }
}

发表于 2022-05-04 18:23:11 回复(0)

Java

MChen-67

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int res = 0;
    while (left < right) {
        if (height[left] >= height[right]) {
            res = Math.max(res, height[right] * (right - left));
            right--;
        } else {
            res = Math.max(res, height[left] * (right - left));
            left++;
        }
    }
    return res;
}

发表于 2022-04-01 10:18:14 回复(0)

Java

笑着活下去丶

public int maxArea (int[] height) {
        // write code here
        if (height.length < 2) return 0;
        int i = 0, j = height.length - 1;
        int maxArea = 0;
        while (i <= j) {
            if (height[i] <= height[j]) {
                maxArea = Math.max(maxArea, height[i] * (j - i));
                i++;
            } else {
                maxArea = Math.max(maxArea, height[j] * (j - i));
                j--;
            }
        }
        return maxArea;
    }

发表于 2022-03-20 10:29:07 回复(0)

Java

菲尼克斯弗兰克

双指针解决类似接雨水问题，不同的是没有小条的宽度可直接计算面积

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

发表于 2022-01-10 11:02:27 回复(0)

提交观点

问题信息

数组双指针

上传者：牛客301499号

难度：

23条回答 357收藏 3141浏览

通过挑战的用户

查看代码

牛客3340351号

2023-03-13 12:24:57
emo的大熊猫...

2023-02-19 22:07:35
牛客11456...

2022-09-20 11:15:39
我知道一个地方

2022-09-18 22:00:12
老唐_

2022-09-18 16:50:48

盛水最多的容器

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题