[LeetCode] Container With Most Water 装最多水的容器

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介:

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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.

这道求装最多水的容器的题和那道 Trapping Rain Water 收集雨水 很类似,但又有些不同,那道题让求整个能收集雨水的量,这道只是让求最大的一个的装水量,而且还有一点不同的是,那道题容器边缘不能算在里面,而这道题却可以算,相比较来说还是这道题容易一些,我们需要定义i和j两个指针分别指向数组的左右两端,然后两个指针向中间搜索,每移动一次算一个值和结果比较取较大的,容器装水量的算法是找出左右两个边缘中较小的那个乘以两边缘的距离,代码如下:

C++ 解法一:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            res = max(res, min(height[i], height[j]) * (j - i));
            height[i] < height[j] ? ++i : --j;
        }
        return res;
    }
};

Java 解法一:

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

这里需要注意的是,由于Java中的三元运算符A?B:C必须须要有返回值,所以只能用if..else..来替换,不知道Java对于三元运算符这么严格的限制的原因是什么。

下面这种方法是对上面的方法进行了小幅度的优化,对于相同的高度们直接移动i和j就行了,不再进行计算容量了,参见代码如下:

C++ 解法二:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            int h = min(height[i], height[j]);
            res = max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
};

Java 解法二:

public class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while (i < j) {
            int h = Math.min(height[i], height[j]);
            res = Math.max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
}

本文转自博客园Grandyang的博客,原文链接:装最多水的容器[LeetCode] Container With Most Water ,如需转载请自行联系原博主。

目录
打赏
0
0
0
0
5351
分享
相关文章
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
|
3月前
|
Leetcode第十一题(盛最多水的容器)
LeetCode第十一题要求找出两条线,使得它们与x轴构成的容器能盛最多的水,通常使用双指针法来解决,通过移动较短的一边来尝试增加容量。
24 0
Leetcode第十一题(盛最多水的容器)
LeetCode第11题盛最多水的容器
该文章介绍了 LeetCode 第 11 题盛最多水的容器的解法,通过分析得出只能移动短板才可能使面积变大的规律,使用双指针法解决该问题,避免了穷举法的高时间复杂度,并总结了算法题需要多实践、思考和积累技巧来提升解题能力。
LeetCode第11题盛最多水的容器
|
5月前
|
【Leetcode刷题Python】11. 盛最多水的容器
解决LeetCode "盛最多水的容器" 问题的Python实现代码,使用了双指针的方法来找出能够容纳最多水的两条线。代码中定义了两个指针i和j,分别从数组的两端向中间遍历,通过计算两个指针所指高度的较小值与它们之间的距离的乘积来更新最大面积res。
39 0
云上应用管理问题之为什么很多业务会采用包年包月 + 按量付费的混合付费方式
云上应用管理问题之为什么很多业务会采用包年包月 + 按量付费的混合付费方式
在k8S中,初始化容器(init container)概念原理是什么?
在k8S中,初始化容器(init container)概念原理是什么?
力扣经典150题解析之二十八:盛最多水的容器
力扣经典150题解析之二十八:盛最多水的容器
68 0
【LeetCode刷题】快乐数、盛水最多的容器
【LeetCode刷题】快乐数、盛水最多的容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等