首页 > 试题广场 >

装最多水的容器

[编程题]装最多水的容器
  • 热度指数:16112 时间限制: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
给定n个非负整数a1,a2,...,an,其中每个表示在坐标(i,ai)的一个点。 Ñ垂直线绘制,使得线的两个端点i是在(i,ai)和(i,0)。找到两条线,其与X轴一起形成了一个容器,使得所述容器包含最多的水。注意:您可能不倾斜的容器。

(i,ai)  i表示在X轴上的位置,ai表示高度,题目的意思是有n个高度为ai的竖线,分别在x轴的i的位置,任意取两条竖线和x轴构成最大的容器,就是面积最大,应为不能为倾斜的容器所以只用求构成长方形的最大面积
class Solution {
public:
    int maxArea(vector<int> &height) {
        if(height.size()<=1)
            return 0;
        int st=0,end=height.size()-1,v=0,max_v=0;
        while(st<end){
            v=(end-st)*(height[st]>height[end]?height[end]:height[st]);
            max_v=v>max_v?v:max_v;
            if(height[st]>height[end])
                end--;
            else
                st++;
        }
        return max_v;
    }
};

发表于 2016-05-23 16:37:12 回复(0)
更多回答
这题最关键的是两点,一是两边往中间找,二是每次放弃最短的版。
这么做的原因在于:从起点和终点开始找,宽度最大,这时每移动一次其中一个点,必然宽度变小。
如此一来,想求最大,只有高度增长才有可能做到,去掉限制----短板,即放弃高度较小的点。
编辑于 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)
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)
//貌似简单,仔细一想有点难,但是其实很简单。
//这是逼近算法么?不是把`~~
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)
//贪心算法:从两边逼近最优解 
//正确性证明:
//假设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)
    /*
    * 目的:最大的容器能装多少水
    * 方法:从两边逼近
    */
    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)
有两种方法。
第一种是把每一条边作为最短边的面积最大的矩形找出来,依次比较取最大(可以优化)。
第二种是从两端开始向中间逼近找全局最优,每次移动较短边(移动较长边可能会导致下一个矩形因为短边限制取不到最优)。
/**
 * 
 * @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)
#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)
//设置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)
    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)
  • 这题在一分钟内就想了个笨方法,迅速敲完,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)
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)
/*
思路:

双指针:头尾指针

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

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

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

*/
#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)
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)
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)
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)
        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)
/**
  * 
  * @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)