【算法】11. 盛最多水的容器(多语言实现)

举报
二当家的白帽子 发表于 2023/12/04 11:22:17 2023/12/04
【摘要】 11. 盛最多水的容器:给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明: 你不能倾斜容器。 样例 1:输入: [1,8,6,2,5,4,8,3,7] 输出: 49 解释: 图中垂直线代表输入数组 ...

11. 盛最多水的容器:

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i])

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明: 你不能倾斜容器。

样例 1:

输入:
	[1,8,6,2,5,4,8,3,7]
	
输出:
	49 
	
解释:
	图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

样例 2:

输入:
	height = [1,1]

输出:
	1

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

原题传送门:

https://leetcode.cn/problems/container-with-most-water/description/


分析

  • 面对这道算法题目,二当家的陷入了沉思。
  • 最终放多少水,只和宽度,高度有关。
  • 由于有两个变量,所以很难一下判断如何才能最大。
  • 我们不妨先让一个量最大,这样结果就只和另一个量有关了。
  • 我们先取最左和最右两个端点构成容器,这时候容器的宽度最大,高度只能是两个端点较小的一个,记录下来盛水量。
  • 下一步,我们将较小的一个端点向中间移动,宽度会缩小,所以我们希望能找到更高的端点,如果移动较高的端点,那么容器的高度不会变高,因为被低的那个端点限制了,所以我们应该移动那个低的端点,这样才有希望找到更高的端点,使得容器整体变高。

题解

rust

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut maxArea = 0;
        let mut l = 0;
        let mut r = height.len() - 1;
        while l < r {
            let mut area;
            if height[l] < height[r] {
                area = (r - l) as i32 * height[l];
                l += 1;
            } else {
                area = (r - l) as i32 * height[r];
                r -= 1;
            }
            maxArea = maxArea.max(area);
        }
        return maxArea;
    }
}

go

func maxArea(height []int) int {
    maxArea := 0
	l := 0
	r := len(height) - 1
	for l < r {
		var area int
		if height[l] < height[r] {
			area = (r - l) * height[l]
			l++
		} else {
			area = (r - l) * height[r]
			r--
		}
		if area > maxArea {
			maxArea = area
		}
	}
	return maxArea
}

c++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int l = 0, r = height.size() - 1;
        while (l < r) {
            int area;
            if (height[l] < height[r]) {
                area = (r - l) * height[l++];
            } else {
                area = (r - l) * height[r--];
            }
            maxArea = max(maxArea, area);
        }
        return maxArea;
    }
};

java

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

typescript

function maxArea(height: number[]): number {
    let maxArea = 0;
	let l       = 0, r = height.length - 1;
	while (l < r) {
		let area;
		if (height[l] < height[r]) {
			area = (r - l) * height[l++];
		} else {
			area = (r - l) * height[r--];
		}
		maxArea = Math.max(maxArea, area);
	}
	return maxArea;
};

python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0
        while l < r:
            if height[l] < height[r]:
                area = (r - l) * height[l]
                l += 1
            else:
                area = (r - l) * height[r]
                r -= 1
            ans = max(ans, area)
        return ans


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://bbs.huaweicloud.cn/community/usersnew/id_1628396583336561 博客原创~


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。