千锋教育-做有情怀、有良心、有品质的职业教育机构

400-811-9990
手机站
千锋教育

千锋学习站 | 随时随地免费学

千锋教育

扫一扫进入千锋手机站

领取全套视频
千锋教育

关注千锋学习站小程序
随时随地免费学习课程

当前位置:北京千锋IT培训  >  技术干货  >  大数据技术干货  > 算法题(力扣)--盛水最多的容器

算法题(力扣)--盛水最多的容器

来源:千锋教育
发布人:qyf
时间: 2022-11-08 14:36:24

  题目描述:

  给你n个非负整数a1,a2,...,an,每个数代表坐标中的一个点(i,ai)。在坐标内画n条垂直线,

  垂直线i的两个端点分别为(i,ai)和(i,0)。找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。

  说明:你不能倾斜容器,且n的值至少为2。

  示例:

  输入:[1,8,6,2,5,4,8,3,7]

  输出:49

  我们都应该听说过木桶原理,一个木桶可以装入多少水取决于最短的那块板;而这道题也可以与木桶装水的问题对应上。 很容易的可以得到---->容器可以容纳水的容量=两条垂直线中最短的那条*两条线之间的距离 现在的情况是,有很多条线,让你计算两两之间能装的最多的水,其实暴力法之间就能解决这个问题,但是它的时间复杂度也达到了O(n^2)

  ok,那我们先试试用暴力法来解 决问题:

  1.暴力法

  直接上代码:

1

  暴力法是可以通过测试的,但是可以看到程序执行用时并不理想

  执行用时 :440 ms, 在所有 Java 提交中击败了17.44% 的用户

  内存消耗 :39.9 MB, 在所有 Java 提交中击败了37.86%的用户

  2.双指针

  思路:使用两个指针(resource和last)分别指向数组的第一个元素和最后一个元素,然后我们计算这两条“线”之间能容纳的水的容量,并更新最大容量(初始值为0);接着我们需要将指向元素值小的那个指针前移一步,然后重复上面的步骤,直到resource = last循环截止。

  来看看代码:

2

  可以很明显的看到,虽然内存消耗两者是差不多的,但是双指针的速度比暴力解法的速度可是高出好多倍。

  时间复杂度:O(n) 空间复杂度:O(1)

  执行用时 :3 ms, 在所有 Java 提交中击败了92.69% 的用户

  内存消耗 :40.3 MB, 在所有 Java 提交中击败了7.86%的用户

声明:本站稿件版权均属千锋教育所有,未经许可不得擅自转载。

10年以上业内强师集结,手把手带你蜕变精英

请您保持通讯畅通,专属学习老师24小时内将与您1V1沟通

免费领取

今日已有369人领取成功

刘同学 138****2860 刚刚成功领取
王同学 131****2015 刚刚成功领取
张同学 133****4652 刚刚成功领取
李同学 135****8607 刚刚成功领取
杨同学 132****5667 刚刚成功领取
岳同学 134****6652 刚刚成功领取
梁同学 157****2950 刚刚成功领取
刘同学 189****1015 刚刚成功领取
张同学 155****4678 刚刚成功领取
邹同学 139****2907 刚刚成功领取
董同学 138****2867 刚刚成功领取
周同学 136****3602 刚刚成功领取

猜你喜欢LIKE

算法题(力扣)--盛水最多的容器

2022-11-08

nio和bio的区别为啥nio好?

2022-11-08

算法题(力扣)两数之和

2022-11-08

最新文章NEW

算法题(力扣)-有效的括号

2022-11-14

DAU(日活)为何会骤降?给出分析思路

2022-11-14

算法题(力扣)--K个一组翻转链表

2022-11-08

相关推荐HOT

快速通道 更多>>

最新开班信息 更多>>

网友热搜 更多>>