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

写在前边:

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

PS:从第10期开始,代码以图片形式给出,方便手机用户阅读,避免左右滑不便阅读,完整代码会上传QQ群【744508600】,当期同步分享到微信群。


No.11 盛最多水的容器

原题:

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线,使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 注意:你不能倾斜容器,n 至少是2。【这里返回值返回area面积即可】

题目分析:

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

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

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

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

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

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

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

原文发布于微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文发表时间:2018-06-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

01:谁考了第k名 个人博客:doubleq.win

个人博客:doubleq.win 01:谁考了第k名 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 在一次考试中,每个学...

36650
来自专栏mathor

LeetCode69. x 的平方根

 这道题直接一个return Math.sqrt就出来了,但是秉承着学习的心态,尝试着用二分法ac  首先要确定的就是左右区间,左区间是0无疑了,那么右...

21520
来自专栏灯塔大数据

每周学点大数据 | No.12数据流中的频繁元素

No.12期 数据流中的频繁元素 Mr. 王:我们再来讲一个例子,数据流中的频繁元素。我们先来说说大数据的数据流模型。 小可:数据流,是流动的数据的意思吗?和...

33070
来自专栏java 成神之路

高亮标红

30580
来自专栏大数据挖掘DT机器学习

从互联网巨头数据挖掘类招聘笔试题目看我们还差多少

1 从阿里数据分析师笔试看职业要求 以下试题是来自阿里巴巴招募实习生的一次笔试题,从笔试题的几个要求我们一起来看看数据分析的职业要求。 一、异常值是指什么?请列...

39570
来自专栏漫漫深度学习路

pytorch: 常见bug与debug

本博文用来记录自己的 pytorch 踩坑过程,虽然 pytorch 命令式编程,声称容易 debug,可是 代码给出的错误提示可是令人相当头疼,所以在本文中记...

45280
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

32650
来自专栏swag code

编程:判断一个数是否是奇数?(93.7%的人会写错)

看似是对的,但是每执行四次(四分之一错误)便会有一个错误的结果(用数据说话)。考虑到负奇数的情况,它除以2的结果就不会是1。因此,返回值是false,而这样是不...

9540
来自专栏机器学习和数学

[数据结构和算法]《算法导论》动态规划笔记(1)

动态规划是求解最优化问题的方法,这类问题有很多可行解,每个解都有一个值,我们希望寻找具有最优值的解。我们称这个解为问题的一个最优解,而不是最优解,因为可能有多个...

402100
来自专栏小樱的经验随笔

鸽巢原理(抽屉原理)的详解

抽屉原理 百科名片 ? 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”...

51470

扫码关注云+社区

领取腾讯云代金券