Leetcode打卡 | No.011 盛最多水的容器

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: 欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

No.11 盛最多水的容器  

原题:

给定 n 个非负整数 a1a2,...,an,每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线,使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

注意:你不能倾斜容器,n 至少是2。【这里返回值返回area面积即可】

题目分析:

这一题可以画一个平面直接坐标系,就显得很清楚啦!关键在于面积的表示!难点在于算法的思路,如何能够提高效率。这一题,只能算中等偏下的难度吧!首先分析下盛最多水是什么意思,也就是如何衡量容器容量!画坐标系如下:

24.jpg

容量,相信所有人都知道底面积乘以高即可。这里又可以理解成木桶效应,决定容量的高取决于短板!哲理噢小伙伴们!这里的容量就可以用面积来衡量,用公式表示即:

area = (j-i)*min(height[i],height[j])

方法一:暴力法!两层循环遍历所有可能,返回最大面积即可!做过太多类似的就不具体介绍 。代码如下:

25.jpg


然而,测试可行,提交发现有些样例无法通过,会超时噢:

26.jpg


原因你懂得!两层循环遍历所有的可能,计算量很大噢。有这样一种双指针的方法,分别指向列表的两端,逐步向中间逼近,最后返回最大值。而逼近的方法是较高的那头不动,较低的那头向高的那头移动(向大佬低头!)原因很容易理解哈。代码实现如下,解释见代码注释:

27.jpg


这种方法效果还不错,可以吃鸡噢!


28.jpg


相关文章
|
3月前
|
容器
Leetcode第十一题(盛最多水的容器)
LeetCode第十一题要求找出两条线,使得它们与x轴构成的容器能盛最多的水,通常使用双指针法来解决,通过移动较短的一边来尝试增加容量。
20 0
Leetcode第十一题(盛最多水的容器)
|
5月前
|
算法 容器
LeetCode第11题盛最多水的容器
该文章介绍了 LeetCode 第 11 题盛最多水的容器的解法,通过分析得出只能移动短板才可能使面积变大的规律,使用双指针法解决该问题,避免了穷举法的高时间复杂度,并总结了算法题需要多实践、思考和积累技巧来提升解题能力。
LeetCode第11题盛最多水的容器
|
5月前
|
Python 容器
【Leetcode刷题Python】11. 盛最多水的容器
解决LeetCode "盛最多水的容器" 问题的Python实现代码,使用了双指针的方法来找出能够容纳最多水的两条线。代码中定义了两个指针i和j,分别从数组的两端向中间遍历,通过计算两个指针所指高度的较小值与它们之间的距离的乘积来更新最大面积res。
35 0
|
7月前
|
算法 测试技术 程序员
力扣经典150题解析之二十八:盛最多水的容器
力扣经典150题解析之二十八:盛最多水的容器
60 0
|
7月前
|
容器
11.盛最多水的容器
11.盛最多水的容器
|
7月前
|
算法 容器
【LeetCode刷题】快乐数、盛水最多的容器
【LeetCode刷题】快乐数、盛水最多的容器
|
7月前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
|
8月前
|
算法 容器
【优选算法】—Leetcode—11—— 盛最多水的容器
【优选算法】—Leetcode—11—— 盛最多水的容器
|
26天前
|
监控 NoSQL 时序数据库
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
188 77