首页 > 试题广场 >

装最多水的容器

[编程题]装最多水的容器
  • 热度指数：16185 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定n个非负整数a1，a2，…，an，其中每个数字表示坐标(i, ai)处的一个点。以（i，ai）和（i，0）（i=1,2,3...n）为端点画出n条直线。你可以从中选择两条线与x轴一起构成一个容器，最大的容器能装多少水？
注意：你不能倾斜容器
例如：
输入 [1,8,6,2,5,4,8,3,7]
输出: 49
示例1

输入

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

输出

49
算法知识视频讲解
添加回答
汉文头像 汉文
这题最关键的是两点，一是两边往中间找，二是每次放弃最短的版。
这么做的原因在于：从起点和终点开始找，宽度最大，这时每移动一次其中一个点，必然宽度变小。
如此一来，想求最大，只有高度增长才有可能做到，去掉限制----短板，即放弃高度较小的点。
编辑于 2016-10-15 16:42:20 回复(6)
元气の悟空头像 元气の悟空 
class Solution {
public:
    int maxArea(vector<int> &height) {
        int l,r,Max=-9999;
        for(l=0,r=height.size()-1;l<r;)
        {
            Max=max(Max,(r-l)*min(height[l],height[r]));
            height[l]<height[r]?l++:r--;
        }
        return Max;
    }
};

发表于 2016-08-19 17:55:29 回复(1)
shijiacheng头像 shijiacheng 
public class Solution {
    public int maxArea(int[] height) {
        if (height.length<2){
            return 0;
        }

        int left = 0;
        int right = height.length-1;
        int maxV = 0;

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

        return maxV;
    }
}
发表于 2018-05-11 21:07:38 回复(0)
324134134143428头像 324134134143428 
//貌似简单，仔细一想有点难，但是其实很简单。
//这是逼近算法么？不是把`~~
for(int i = 0,j = height.size()-1;i<j;)
{
     MAXI = max(min(height[i],height[j])*(j-i),MAXI);
     height[i]>height[j]?j--:i++;
}

发表于 2017-11-11 10:45:25 回复(4)
为你扣下F键头像 为你扣下F键
//贪心算法：从两边逼近最优解 
//正确性证明:
//假设x，y为最优解，i向右逐渐靠近x，j向左逐渐靠近y，那么i没有可能跳过x，j也没有可能跳过y； 
//1、当j==y,i<x时,那么此时必定有height[i]<height[j],如果不是这样,i值就比x值更优,与假设矛盾,即必定是i向右移动直到i==x；
//2、当x==x,j>y时,同理； 

编辑于 2018-08-09 18:35:19 回复(0)
C/C++
努力的牛牛头像 努力的牛牛 
    /*
    * 目的：最大的容器能装多少水
    * 方法：从两边逼近
    */
    int maxArea(vector<int> &height) {
        int maxVal = 0;
        int left =0,right = height.size()-1;
        while(left<right){
            if (height[left]<=height[right]){
                maxVal = max(maxVal,(right-left)*height[left]);
                left++;
            }
            else{
                maxVal = max(maxVal,(right-left) * height[right]);
                right--;
            }
        }
        return maxVal;
    }
发表于 2019-12-11 14:45:47 回复(0)
Java
ChopinXBP头像 ChopinXBP
有两种方法。
第一种是把每一条边作为最短边的面积最大的矩形找出来，依次比较取最大（可以优化）。
第二种是从两端开始向中间逼近找全局最优，每次移动较短边（移动较长边可能会导致下一个矩形因为短边限制取不到最优）。 
/**
 * 
 * @author ChopinXBP
 * 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.
 * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * 说明：你不能倾斜容器，且 n的值至少为 2。
 *
 */

public class ContainerWithMostWater {     public static void main(String[] args) {         // TODO Auto-generated method stub         int[] height = {1,8,6,2,5,4,8,3,7};         int[] height2 = {1,2,4,3};         System.out.println(maxArea(height));         System.out.println(maxArea(height2));         System.out.println(maxArea2(height));         System.out.println(maxArea2(height2));     }     //对每一条线段i，找左右两端距离i最长的不小于i的长度的线段j。j作为长，i作为宽，ij构成的矩形是包含线段i的面积最大的矩形。
    public static int maxArea(int[] height) {
        int result = 0;
        
        for(int i = 0; i < height.length; i++) {
            int num = height[i];
            int longest = 0;
                         int idx = 0;
            while(idx < i) {
                if(height[idx] >= num) {
                    longest = i - idx;
                    break;
                }
                idx++;
            }
            idx = height.length - 1;
            while(idx > i && idx - i > longest) {
                if(height[idx] >= num) {
                    longest = idx - i;
                    break;
                }
                idx--;
            }
                         if(num * longest > result) {
                result = num * longest;
            }
        }
        
        return result;
    }
    
    //设置left和right从两端逼近，每次计算其和较短边围成的矩形的面积，之后移动较短边。逼近过程中最大的矩形面积即为所求。
    public static int maxArea2(int[] height) {
        int result = 0;
        
        int right = height.length - 1;
        int left = 0;
        
        while(left < right) {
            int shorter = height[right] < height[left] ? height[right] : height[left];
            if((right - left) * shorter > result) {
                result = (right - left) * shorter;
            }
            //每次移动较短边（移动较长边可能会导致下一个矩形因为短边限制取不到最优）
            if(height[right] < height[left]) {
                right--;
            }else {
                left++;
            }
        }
        
        return result;
    }
}


	


 

发表于 2019-02-22 20:51:43 回复(0)
xiao_lai头像 xiao_lai 
#include<math.h>
class Solution {
public:
    int maxArea(vector<int> &height) {
        //Note: You may not slant the container.
        //暴力搜索,时间复杂度为O(n^2)   (120ms)
        /*
        int result=0;
        int size = height.size();
        for(int i=0;i<size;i++){
            for(int j=i+1;j<size;j++){
                int area = (j-i)*min(height[i],height[j]);
                if(area>result)result = area;
            }
        }
        return result;
        */
        
        //方式二：贪心算法策略(10ms)
        int result=0;
        if(height.size()<=1) return result;  //无法构成容器
        int i=0,j=height.size()-1;
        while(i<j){
            int area = (j-i)*min(height[i],height[j]);
            if(area>result)result = area;
            if(height[i]>height[j]){
                j--;
            }else{
                i++;
            }
            
        }
        return result;

        
    }
};

发表于 2016-06-24 23:11:48 回复(0)
Java
HW柯可头像 HW柯可 
//设置left、right两个下标，代表左右两条直线，从两端开始遍历，对于两条直线和X轴所形成的的容器，若左边的直线高度大于右边的直线高度，则右边直线下标right--,反之左边下标直线下标left++。
//因为容器所成盛水的体积等于宽度（right-left）乘以较低的直线高度，淘汰较低的直线高度，尝试寻找更高的直线高度，继而尝试寻找更大的体积。
public class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length == 0)
            return 0;
        int left = 0;
        int right = height.length - 1;
        int max_area = 0;
        int area = 0;
        while(left < right){
            if(height[left] > height[right]){
                area = height[right] * (right - left);
                right--;
            }
            else{
                area = height[left] * (right - left);
                left++;
            }
            if(area > max_area){
                max_area = area;
            }
        }
        return max_area;
    }
}

编辑于 2019-07-16 12:05:57 回复(1)
风中追风20180314092925头像 风中追风20180314092925 
    int maxArea(vector<int>& height) {
        int res = 0, l = 0, r = height.size() - 1;
        while(l < r){
            res = max(res, (r-l)*min(height[l], height[r]));
            if(height[l] < height[r])
                ++l;
            else
                --r;   
        }
        return res;
    }

发表于 2019-05-02 19:36:45 回复(0)
小小呢头像 小小呢 
/*
     * 贪心算法：从两边开始向中间缩小;每一步比较左右边界高度,高度小的那个向里走一步
     * 
     * 这个贪心算法,为什么最优解不会被错过？         反证法 假设会被错过。
     *         假设最优解是横坐标为x1,x2(x2在右边)的这两个点组成的
     *               只考虑扫描到x2时,x1被错过的情况(x2被错过同理)：
     *         被错过指的是 当右指针向左扫描经过x2之后,左指针还在x1的左边P处时,x1被错过。
     * 
     *                     情况一   x2>p:  x2会被保留,然后左指针向右移动到x1,x1不会被错过
     *                     情况二   x2<p:  小情况一：height[p]>height[x1]    则最优解为 p,x2而不是 x1,x2。  假设不成立
     *                                   小情况二：p<=x1  最优解还是p,x2。 假设不成立
     *                             //因为x2比p和x1都小,所以容器高度取决于x2,而p比x1偏左,所以p,x2比x1,x2面积大
     *                         
     *        
     */
    public int maxArea(int[] height) {
        if(height.length<=2) return 0;
        
        int left=0,right=height.length-1;
        int maxArea=0;
        while(left<right) {
            int area = Math.min(height[left],height[right])*(right-left);
            maxArea = Math.max(maxArea, area);
            if(height[left]<=height[right]) {
                left++;
            }else {
                right--;
            }
        }
        return maxArea;
    }

发表于 2018-06-12 16:07:20 回复(0)
玩归玩闹归闹别拿offer开玩笑头像 玩归玩闹归闹别拿offer开玩笑
  • 这题在一分钟内就想了个笨方法，迅速敲完，KO！
  • 因为题目还是很简单，不考虑将装水的容器倾斜，所以只要考虑梯形中最短的边和底边的乘积就行了：正反两遍循环数组，第一遍从0~len，先固定最左边的边，从右往左遍历数组，如果碰到大于等于最左边边长的边，那就判断是否大于当前的最大盛水体积并跟新，然后就停止这次循环，将最左边的边向右移动一格，重复操作；第二遍从len~0,和第一遍一样。 
public class Solution {
    public int maxArea(int[] height) {
        int len=height.length;
        if(len==0){
            return 0;
        }
        int maxW=0;
        for(int i=0;i<len;i++){
            for(int j=len-1;j>i;j--){
                if(height[j]>=height[i]){
                    if(height[i]*(j-i)>maxW){
                        maxW=height[i]*(j-i);
                    }
                    break;
                }
            }
        }
        for(int i=len-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(height[j]>=height[i]){
                    if(height[i]*(i-j)>maxW){
                        maxW=height[i]*(i-j);
                    }
                    break;
                }
            }
        }
        return maxW;
    }
}
发表于 2018-04-30 19:46:43 回复(1)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    int maxArea(vector<int> &height) {
        int s,maxArea = 0;
        int l=0,r=height.size()-1;
        while(l<r){
            s = (r-l)*min(height[l],height[r]);
            if(s > maxArea)
                maxArea = s;
            if(height[l]>height[r])
                r--;
            else
                l++;
        }
    	return maxArea;
    }
};

发表于 2017-07-22 01:38:31 回复(0)
C++
好菜啊我头像 好菜啊我 
/*
思路：

双指针：头尾指针

头指针从前向后移动，尾指针从后向前移动。

计算头尾指针之间的面积，并于当前最大面积比较。

头尾指针总有一个指向较小值，因此可以每次都把指向较小值的指针进行移动。

*/
#include <algorithm>
class Solution {
public:
    /**
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        //特殊情况检测
        if(height.size()==0){
            return maxArea;
        }

        int i=0;
        int j=height.size()-1;

        //头尾指针移动
        while(i<j){
            //用较短的作为宽
            int wide = (height[i]>height[j])?height[j]:height[i];
            //头尾指针的间隔是长
            int length = j-i;

            //计算面积
            maxArea = max(length*wide,maxArea);

            //将较短指针后移
            if(height[i]<height[j]){
                i++;
            }else{
                j--;
            }
        }

        return maxArea;
    }
};

发表于 2023-04-10 17:02:52 回复(0)
杨益良头像 杨益良
两边逼近 小的移动终止条件左大于等于右边
发表于 2021-07-19 09:05:22 回复(0)
牛客843298998号头像 牛客843298998号 
import java.util.*;


public class Solution {
    /**
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] height) {
        // write code here
        int sum=0,max=0;
		for (int i = 0; i < height.length; i++) {
			int count=1;
			for (int j = i+1; j < height.length; j++) {
				if(height[i]<height[j]) {
					sum=count*height[i];
				}else {
					sum=count*height[j];
				}
				max=Math.max(sum, max);
				count++;
			}
		}
        return max;
    }
}

发表于 2021-03-26 17:50:09 回复(0)
Tod_头像 Tod_ 
import java.util.*;


public class Solution {
    /**
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] height) {
        // write code here
        int left = 0, right = height.length-1;
        int res = 0;
        while(left<right){
            int h = height[left]<height[right]?height[left]:height[right];
            if(res < h*(right-left)){
                res = h*(right-left);
            }
            if(height[left]<height[right]) {
                left++;
            }else{
                right--;
            }
        }
        return res;
    }
}


发表于 2021-03-11 14:49:16 回复(0)
一叶舟troy头像 一叶舟troy 
class Solution {
public:
    /**
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
     int left = 0;
     int right = height.size()-1;
     int maxArea = 0;
        
     while(left < right )
     {
        //最短 
         if(height[left] < height[right])
         {
             maxArea =max(maxArea,height[left]*(right-left));
             left ++;//减少遍历次数
         }else
         {
              maxArea =max(maxArea,height[right]*(right-left));
              right --;//减少遍历次数
         }
         
        
     }
     return maxArea; //编译减少错误
    }
};

发表于 2021-01-07 16:43:30 回复(0)
Java
坚定的伊登希望奇迹发生头像 坚定的伊登希望奇迹发生
        int max = 0;
        for (int i = 0;  i < height.length;  i++) {
            for (int j = i+1;  j < height.length;  j++) {
                int tall = height[i]>height[j] ? height[j] : height[i];
                max = max>tall*(j-i)?max:tall*(j-i);
            }
        }
        return max;
发表于 2020-08-13 22:17:03 回复(0)
JavaScript
钱多事少离家近offer头像 钱多事少离家近offer 
/**
  * 
  * @param height int整型一维数组 
  * @return int整型
  */
function maxArea( height ) {
    // write code here
    if(!height){
        return 0;
    }
    let max = 0;
    let i = 0;
    let j = height.length - 1;
    while(i < j){
        max = Math.max(max, (j-i)*Math.min(height[i],height[j]));
        if(height[i] < height[j]){
            i++;
        }else{
            j--;
        }
    }
    return max;
}
module.exports = {
    maxArea : maxArea
};

发表于 2020-08-13 21:53:07 回复(0)
提交观点

问题信息

数组 查找
难度：
73条回答 26725浏览

热门推荐

通过挑战的用户

查看代码

相关试题

装最多水的容器

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号