首页 > 试题广场 >

盛水最多的容器

[编程题]盛水最多的容器
  • 热度指数：32735 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水
1.你不能倾斜容器
2.当n小于2时，视为不能形成容器，请返回0
3.数据保证能容纳最多的水不会超过整形范围，即不会超过231-1

数据范围:


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


示例1

输入

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

输出

49
示例2

输入

[2,2]

输出

2
示例3

输入

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

输出

25
算法知识视频讲解
添加回答
牛客212561046号头像 牛客212561046号 
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        int left=0, right=height.size()-1, res=0;
        if(right<1) return res;
        while (left<right) {
            int contains = (right-left)*min(height[left], height[right]);
            if(contains>res){
                res = contains;
            }
            if(height[left]>height[right]){
                int v = height[right];
                right--;
                while (right>left&&height[right]<=v) {
                    right--;
                }
            }else{
                int v = height[left];
                left++;
                while (right>left&&height[left]<=v) { //加速，如果换掉的边界比原来矮，则必不可能盛放更多的水,继续换
                    left++;
                }
            }
        }
        return res;
    }
};

发表于 2023-09-17 12:38:51 回复(0)
Java
wpcAlex头像 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)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // 时间复杂度O(N)，空间复杂度O(1)
        if (height.size() < 2) return 0;
        int left = 0, right = height.size() - 1, res = 0, tmp;
        while (left < right) {
            tmp = min(height[left], height[right]) * (right - left);
            res = res > tmp ? res : tmp;
            if (height[left] < height[right]) ++left;
            else --right;
        }
        return res;
    }
};

发表于 2022-10-25 14:46:34 回复(0)
Java
牛客292107984号头像 牛客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)
C++
几点了奶茶吧头像 几点了奶茶吧 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        int n = height.size();
        if (n < 2) {
            return 0;
        }
        int ans = 0;
        
        int i = 0, j = n-1;
        while (i < j) {
            ans = max(ans, min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) {
                i++;
            }else {
                j--;
            }
        }
        
        return ans;
    }
};

发表于 2022-04-15 20:52:22 回复(0)
Leeston520头像 Leeston520
这道题使用了离散数学的枚举法，把所有可能是最大值收集起来，得出最大者即最大值 
 public int maxArea(int[] height) {
        // write code here
        if (height.length < 2)
            return 0;
        int maxArea = 0;
        int left = 0, right = height.length - 1;
        while (left < right) {
            int currArea = (right - left) * Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, currArea);
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return maxArea;
    }


编辑于 2024-04-12 23:39:56 回复(0)
C++
感谢靓仔赏饭吃头像 感谢靓仔赏饭吃 
#include <type_traits>
class Solution {
  public:
    /**
夹逼定理
     */
    int maxArea(vector<int>& height) {
        int ans = 0;
        int temp = 0;
        int head = 0, tail = height.size() - 1;
        while (head < tail) {
            temp = min(height[head], height[tail]) * (tail - head);
            ans = max(ans, temp);
            if (height[head] > height[tail]) {
                tail--;
            } else {
                head++;
            }
        }
        return ans;
    }
};

编辑于 2024-04-06 16:43:16 回复(0)
JavaScript Node
thinkerer头像 thinkerer 
function maxArea( height ) {
    // write code here
    let l=0,r=height.length-1;
    let max=0;
    while(l<=r){
        const area=(r-l)*Math.min(height[l],height[r]);
        max=Math.max(area,max);

        if(height[l]>height[r]){
            r--
        }else{
            l++
        }
    }
    return max;
}

编辑于 2024-03-20 22:24:46 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
int maxArea(int* height, int heightLen ) {
    // write code here
    int res,i,*j,*heightMax,*heightLeft,*heightRight;
    if(heightLen<2)
        return 0;
   
    heightMax = height;
    for(i=0;i<heightLen;i++) {
        if(*heightMax<height[i])
            heightMax=&height[i];
    }
    heightLeft = heightMax;
    heightRight = heightMax;

    res = 0;
    for(i=heightMax-height,j=heightMax;i>0;i--) {
        long long volume;
        j--;
        volume = (*j) * (heightMax-j);
        if(res<volume) {
            res = volume;
            heightLeft = j;
        }
    }

    res = 0;
    for(i=heightMax-height,j=heightMax;i<heightLen-1;i++) {
        long long volume;
        j++;
        volume = (*j) * (j-heightMax);
        if(res<volume) {
            res = volume;
            heightRight = j;
        }
    }

    res = 0;
    for(i=heightRight-height,j=heightRight;i>0;i--) {
        long long volume;
        j--;
        volume = (*j>*heightRight?*heightRight:*j) * (heightRight-j);
        if(res<volume) {
            res = volume;
            heightLeft = j;
        }
    }

    res = 0;
    for(i=heightLeft-height,j=heightLeft;i<heightLen-1;i++) {
        long long volume;
        j++;
        volume = (*j>*heightLeft?*heightLeft:*j) * (j-heightLeft);
        if(res<volume) {
            res = volume;
            heightRight = j;
        }
    }

    res = (*heightLeft) * (heightMax-heightLeft);
    res = (*heightRight) * (heightRight-heightMax) > res ? (*heightRight) * (heightRight-heightMax) : res;
    res = (*heightLeft>*heightRight ? *heightRight: *heightLeft) * (heightRight-heightLeft) > res ? (*heightLeft>*heightRight ? *heightRight: *heightLeft) * (heightRight-heightLeft) : res;

    return res;
}

编辑于 2024-03-13 15:25:46 回复(0)
Go
老小羊肖恩头像 老小羊肖恩 
package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param height int整型一维数组
 * @return int整型
 */
func maxArea( height []int ) int {
    // write code here
    if len(height) < 1 {return 0}

    res, l, r := 0, 0, len(height) - 1
    for l < r {
        res = getMax(res, getMin(height[l], height[r]) * (r - l))
        if height[l] <= height[r] {
            l ++
        } else {
            r --
        }
    }
    return res
}

func getMin(l, r int) int {
    if l <= r {
        return l
    }
    return r
}

func getMax(res, tmp int) int {
    if res < tmp {
        return tmp
    }
    return res
}

编辑于 2024-03-06 02:45:03 回复(0)
Panzer_Jack头像 Panzer_Jack 
 int maxArea(vector<int>& height) {
        // write code here
        int l = 0, r = height.size() - 1;
        int res = 0;

        while(l < r) {
            res = max(res, min(height[l], height[r]) * (r - l));
            if(height[l] < height[r]) l++;
            else r--;
        }
        return res;
 }

发表于 2024-02-28 14:19:31 回复(0)
余生还长着呢头像 余生还长着呢 
import java.util.*;


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

        // 初始化指针
        int left = 0;
        int right = height.length - 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;
    }
}

发表于 2024-02-05 10:02:27 回复(0)
牛客2024007号头像 牛客2024007号 
import java.util.*;


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

编辑于 2024-01-18 10:29:57 回复(0)
C++
牛客706368877号头像 牛客706368877号 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param height int整型vector
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        int n = height.size();
        if (n < 2) {
            return 0;
        }
        if (n == 2) {
            return min(height[0], height[1]);
        }

        int maxV = 0;
        int i = 0, j = n - 1;
        bool moveI = true;
        while (i < j) {
            int v = min(height[i], height[j]) * (j - i);
            if (v > maxV) {
                maxV = v;
            }

            if (height[i] <= height[j]) {
                int curVal = height[i];
                ++i;
                while (i < j && height[i] <= curVal) {
                    ++i;
                }
            } else {
                int curVal = height[j];
                --j;
                while (i < j && height[j] <= curVal) {
                    --j;
                }
            }
        }

        return maxV;
    }
};

发表于 2023-09-22 10:56:54 回复(0)
C++
牛客541678616号头像 牛客541678616号
左右壁，得到各自第一个变高的位置，选择最能让容器高度增长的一边移动 
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        if(n<2)return 0;//判空

        int l=0,r=n-1;
        int maxx = (r-l)*min(height[l],height[r]);
        int templ = l,tempr = r;
        while(l<r)
        {
            if(templ==l)
                while(templ<r&&height[templ]<=height[l])++templ;
            if(tempr==r)
                while(l<tempr&&height[tempr]<=height[r])--tempr;

            if(min(height[templ],height[r])>min(height[l],height[tempr]))
                    l=templ;
                else
                    r=tempr;
            maxx =max(maxx,(r-l)*min(height[l],height[r]));
        }
        return maxx;
    }
};
发表于 2023-08-30 20:14:43 回复(0)
算法小白一枚555头像 算法小白一枚555 
//问题描述：
//给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水
//1.你不能倾斜容器
//2.当n小于2时，视为不能形成容器，请返回0
//3.数据保证能容纳最多的水不会超过整形范围，即不会超过2^31-1
#include "vector"
#include "iostream"
using namespace std;

//分析：
//我们希望通过移动指针来寻找更高的高度，以期望获得更大的容积。
//所以，如果height[left]小于height[right]，那么无论怎样移动right指针，
//容器的高度都不会超过height[left]，所以移动right指针对于容积的增加没有任何帮助。
int maxArea(vector<int>& height) {
    int n=height.size();
    if(n<2) return 0;
    int size=0;
    int Max=0;
    int i=0;//左指针
    int j=n-1;//右指针
    while(i<j)
    {
        size=abs(j-i)*min(height[i],height[j]);
        Max=max(Max,size);
        if(height[i]<height[j]) i++;
        else j--;
    }
    return Max;
}

发表于 2023-08-20 19:59:13 回复(0)
姜方木木头像 姜方木木
这个题用双指针，问题是如何修改指针位置（即应该左指针增加还是右指针减小），决定容量（
min(height[lk],height[rk])*(rk-lk);
）的变量本质上是最低高度，和长度（但长度一开始设定为最长），因为长度的变化是减一（要么是左指针增加1要么是右指针减小1），所以谁高度低修改谁;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param height int整型vector
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
         int n=height.size();
        // vector<int> dpl(n);
        // vector<int> dpr(n);
        // dpl.push_back(height[0]);
        // dpr.push_back(height[n-1]);
        // for(int i=1;i<n-1;i++){
        //     if(height[i]>height[i-1]){
        //         dpl[i]=height[i];
        //     }else{
        //         dpl[i]=dpl[i-1];
        //     }
        // }
        // for(int i=n-2;i>0;i++){
        //     if(height[i]>height[i+1]){
        //         dpr[i]=height[i];
        //     }else{
        //         dpr[i]=dpr[i+1];
        //     }
        // }
        int lk=0,rk=n-1;
        int res=0,vec;
        while(lk<rk){
            vec=min(height[lk],height[rk])*(rk-lk);
            res=max(res,vec);
            int leftdecline=height[lk+1]-height[lk];
            int rightdecline=height[rk-1]-height[rk];
            if(height[lk]<height[rk]){
                lk++;
            }else {
            rk--;
            }
        }
        return res;
    }
};
发表于 2023-08-10 10:26:18 回复(0)
C++
牛客665296323号头像 牛客665296323号
答案双指针不完全对吧？碰到测试集[3,1,5,6,2,3],用 max(ans, min(height[i], height[j]) * (j - i)) 解出来的答案不对，一开始的计算两边短板都是3，根据答案计算的临时值是(5-0)*min(3,3)=15，很明显不对，因为中间有个短板1.
发表于 2023-08-03 17:22:51 回复(0)
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)
不让我进拉倒头像 不让我进拉倒 
class Solution:
    def maxArea(self , height: List[int]) -> int:
        # write code here
        if not height: return 0
        left, right = 0, len(height) - 1
        res = 0
        while left < right:
            res = max(res, (right - left) * min(height[left], height[right]))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return res

发表于 2023-07-05 15:12:28 回复(0)
提交观点

问题信息

数组 双指针
上传者：牛客301499号
难度：
52条回答 3112浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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