首页 > 试题广场 >

盛水最多的容器

[编程题]盛水最多的容器
  • 热度指数：42807 时间限制：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
算法知识视频讲解
添加回答
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 回复(3)
TokaiTeio_头像 TokaiTeio_ 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param height int整型vector
     * @return int整型
     */

    struct TokaiTeio {
        int x, i;
        bool operator < (const TokaiTeio& b) const {
            return x < b.x;
        }
        TokaiTeio() : x(0), i(0) {};
    };

    bool cmp(TokaiTeio A, TokaiTeio B) {
        return A.x < B.x;
    }

    int f[200005][22],dp[200005][22];
    int a[200005],b[200005];

    //区间最大
    void work(int n) {
        for (int i = 1; i <= n; i++) f[i][0] = a[i];
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
    int RMQ(int l, int r) {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        return max(f[l][k], f[r - (1 << k) + 1][k]);
    }

//区间最小
    void work2(int n) {
        for (int i = 1; i <= n; i++) dp[i][0] = b[i];
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }
    int RMQ2(int l, int r) {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        return min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }

    int maxArea(vector<int>& height) {
        // write code here
        if (height.size() < 2) return 0;
        int cnt = 0;
        int ans = 0;
        TokaiTeio z[height.size() + 3];
        for (auto it : height) {
            z[++cnt].x = it;
            z[cnt].i = cnt;
        }
        sort(z + 1, z + cnt + 1);
        for(int i = 1; i <= cnt; i ++ ) a[i] = z[i].i;
        for(int i = 1; i <= cnt; i ++ ) b[i] = z[i].i;
        work(cnt);
        work2(cnt);
        int l = 1;
        for(int i = 1; i <= cnt; i ++ )
        {
            if(z[i].x != z[i - 1].x) l = i;
            ans = max({ans,(abs(RMQ(l,cnt) - z[i].i)) * z[i].x,(abs(RMQ2(l,cnt) - z[i].i)) * z[i].x});
        }
        return ans;
    }
};

发表于 2024-08-16 22:53:58 回复(0)
牛客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)
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)
Lryyy头像 Lryyy
为什么 [1,8,6,2,5,4,8,3,7] 的输出是49而不是54啊？？？
1，8*5=40，7*2=14，然后再从中选两个不是40+14=54吗？？？
发表于 2025-05-15 06:55:45 回复(0)
Java
Sen🍓🍀头像 Sen🍓🍀 
import java.util.*;

// @@@ 盛水： 类似接雨水
//           双指针i,j初始两端,每次移动小的那端,遇到更高的更新两端大小关系 & 面积
//           直到i,j相遇
public class Solution {
    public int maxArea (int[] height) {
        if (height.length == 0) return 0;

        int res = 0, i = 0, j = height.length - 1, left = height[i], right = height[j];
        while (i <= j) {
            res = Math.max(res, Math.min(left, right) * (j - i)); // 计算面积
            // System.out.printf("i=%d j=%d %d %d res=%d\n", i, j, height[i], height[j], res);
            // 左端更矮, 移动i
            if (left <= right) {
                while (i <= j && height[i] <= left) {  // 更低高度的,面积肯定更小,略过
                    i++;
                }
                if (i <= j) left = height[i]; // 遇到更高的,更新左端高
            }
            // 右端更矮, 移动j
            else {
                while (i <= j && height[j] <= right) {
                    j--;
                }
                if (i <= j) right = height[j];
            }
        }

        return res;
    }
}

发表于 2025-03-23 09:04:31 回复(0)
Python3
牛客520366559号头像 牛客520366559号 
class Solution:
    def maxArea(self , height: List[int]) -> int:
        # write code here
        '''超时了'''
        # if len(height) < 2:
        #     return 0
        # left = 0
        # res = 0
        # while left < len(height) - 1:
        #     for right in range(left + 1, len(height)):
        #         mianji = min(height[left], height[right]) * (right - left)
        #         res = max(res,mianji)
        #     left = left + 1
        # return res
        '''双指针'''
        left = 0
        right = len(height) - 1
        res = 0
        while left < right:
            mianji = min(height[left], height[right])*(right - left)
            res = max(res, mianji)
            if height[left] < height[right]:
                left = left + 1
            else:
                right = right - 1
        return res

发表于 2025-02-23 23:27:16 回复(0)
C++
君鸿头像 君鸿
int maxArea(vector<int>& height) {
        return maxArea(height, 0, height.size() - 1);
    }

    int maxArea(vector<int>& height, int l, int r) {
        if (l >= r) return 0;
        int minH = min(height[l], height[r]);
        int ans = minH * (r - l);
        if (height[l] == height[r]) {
            return max(ans, maxArea(height, l + 1, r));
        }
        while (height[l] <= minH) ++l;
        while (height[r] <= minH) --r;
        return max(ans, maxArea(height, l, r));
    }
发表于 2024-12-15 14:59:50 回复(0)
Java
渔鱼123头像 渔鱼123 
public class Solution {
    public int maxArea (int[] height) {
        int max = 0;
        int left=0;
        int right=height.length-1;
        while(left<right){
            max=Math.max(max,(right-left)*Math.min(height[left],height[right]));
            if(height[left]<height[right]) left++;
            else right--;
        }
        return max;
    }
}
发表于 2024-10-14 18:46:51 回复(0)
C
秋隔遗音头像 秋隔遗音
int maxArea(int* height, int heightLen ) {
    int i, j, max = 0;
    for (i = 0; i < heightLen - 1; i++)
        for (j = heightLen - 1; j > i; j--)
            if (height[j] >= height[i]) {
                if (height[i] * (j - i) > max)
                    max = height[i] * (j - i);
                break;
            }
    for (i = heightLen - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (height[j] >= height[i]) {
                if (height[i] * (i - j) > max)
                    max = height[i] * (i - j);
                break;
            }
    return max;
}
发表于 2024-08-26 19:53:27 回复(0)
小死神头像 小死神
int maxArea(int* height, int heightLen ) {
  int left=0;
  int right=heightLen-1;
  int di;
  int gao;
  int Area;
  int Area_max=0;
  while(left<right)
  {
     di=right-left;
     gao=(height[left]>height[right])?height[right]:height[left];
     Area=di*gao;
     if(Area>Area_max)
     {
        Area_max=Area;
     }
     if(height[left]>height[right])
     {
        right--;
     }
     else {
       left++;
     }
  }
  return Area_max;
}
发表于 2024-08-09 09:44:06 回复(0)
牛客876546758号头像 牛客876546758号
这个题能不能用动态规划，我这样写会超时
class Solution:
    def maxArea(self, height: List[int]) -> int:
        dp = []

        if len(height) < 2:
            return 0
        else:
            for i in range(len(height)):
                for j in range(i, len(height)):
                    if i == j:
                        pass
                    else:
                        a = min(height[i], height[j])
                        b = j - i
                        dp.append(a * b)

        return max(dp)

发表于 2024-07-30 17:11:01 回复(0)
无名珠头像 无名珠 
int maxArea(int* height, int heightLen ) {
    if (heightLen < 2) return 0; //小于2不能形成容器

    int left = 0;
    int right = heightLen - 1;
    int max = 0; //存放最终的最大容积
    int maxTemp = 0; //存放临时容积
    while (left < right)
    {
        maxTemp = height[left] > height[right] ? \
                  height[right] * (right- left)  \
                 :height[left] * (right- left)   ; //计算每次容积大小
        if (maxTemp > max) max = maxTemp;

        //贪心算法，移动较短边
        if (height[left] > height[right]) --right;
        else ++left;
    }
    return max;
}

发表于 2024-05-26 22:07:52 回复(0)
唐氏综合征头像 唐氏综合征
这道题使用了离散数学的枚举法，把所有可能是最大值收集起来，得出最大者即最大值 
 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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

盛水最多的容器

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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