LeetCode_11_中等_盛最多水的容器

这篇具有很好参考价值的文章主要介绍了LeetCode_11_中等_盛最多水的容器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


1. 题目

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

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

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

说明:你不能倾斜容器。

示例 1:

LeetCode_11_中等_盛最多水的容器,LeetCode进阶之路,leetcode,算法
输入:[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 = = h e i g h t . l e n g t h n == height.length n==height.length
  • 2 < = n < = 1 0 5 2 <= n <= 10^5 2<=n<=105
  • 0 < = h e i g h t [ i ] < = 1 0 4 0 <= height[i] <= 10^4 0<=height[i]<=104

2. 思路及代码实现(Python)

2.1 双指针

这里有一个很直接的方式,就是遍历所有的容器边界组合,一个个对比找到装水最多的,但是这样的算法复杂度为 O ( n 2 ) O(n^2) O(n2),那是否有办法缩减掉一些组合呢?使得我们并不需要遍历所有的组合也能找到容量最大的容器。

这个方法就是双指针,在列表的左右两端生成指针,不断地把指针向中间靠拢,能够覆盖所有地容器边界情况,但是每一次移动指针,都会缩减一部分边界组合,这里就有一个问题,到底需要移动哪个指针?假设有两个指针在列表的 i , j i,j i,j 位置,其中, h e i g h t [ i ] < h e i g h t [ j ] height[i] < height[j] height[i]<height[j],不论我们移动哪一边的指针,容器的长都会减小,且容器的高取决于最矮的边界,因此,对于左指针(较矮)而言,不会有包含左指针的组合且容量还大于当前组合的情况了,因此左指针可以移动。

例如:[3,>2,6,8,3,2,4<],假设左指针在2,右指针在4,此时的容器容量为 5 × 2 = 10 5\times 2=10 5×2=10,显然,不论我们如何移动右指针,只要左指针还是2的位置,那右指针的值可能比4高,或者比4低甚至比2低,但新容器的长都会小于5,且高不会高于2(取边界的较小值),因此固定左指针2之后的容器容量不会再高于10,此时可以舍弃左指针的位置,向右移动。

依次类推,左右指针不断把较小值向中间推移,最终得到的较大容量即为总体最大的容量。此时,由于指针只移动了 n n n 次,因此算法时间复杂度为 O ( n ) O(n) O(n),而移动指针的过程只记录指针位置和当前最大值,空间复杂度为 O ( 1 ) O(1) O(1)

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

执行用时:169 ms
消耗内存:26.77 MB

参考来源:力扣官方题解文章来源地址https://www.toymoban.com/news/detail-820663.html

到了这里,关于LeetCode_11_中等_盛最多水的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|双指针系列No.4】leetcode11. 盛最多水的容器

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(48)
  • 【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字

    盛水最多的容器 (1)暴力解法   算法思路:我们枚举出所有的容器大小,取最大值即可。   容器容积的计算方式:   设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定,因此可得容积公式 :

    2024年02月13日
    浏览(48)
  • 11. 盛最多水的容器

    给定一个长度为  n  的整数数组  height  。有  n  条垂线,第  i  条线的两个端点是  (i, 0)  和  (i, height[i])  。 找出其中的两条线,使得它们与  x  轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明: 你不能倾斜容器。 示例 1: 示例 2: 提示

    2024年01月20日
    浏览(57)
  • 力扣 | 11. 盛最多水的容器

    双指针解法–对撞指针

    2024年01月18日
    浏览(39)
  • 11. 盛最多水的容器(c++题解)

    给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明:你不能倾斜容器。 示例 1: 输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释

    2024年02月11日
    浏览(34)
  • 【力扣算法12】之 11. 盛最多水的容器 python

    给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明 :你不能倾斜容器。 输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂

    2024年02月16日
    浏览(47)
  • 【算法专题--双指针算法】leecode-202. 快乐数(medium)、leecode-11. 盛最多水的容器(medium)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月23日
    浏览(38)
  • 力扣-盛最多水的容器

    11.盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。 说明:你不能倾斜容器 示例1: 示例 2: 分析: 题解

    2024年01月15日
    浏览(41)
  • 「优选算法刷题」:盛最多水的容器

    给定一个长度为  n  的整数数组  height  。有  n  条垂线,第  i  条线的两个端点是  (i, 0)  和  (i, height[i])  。 找出其中的两条线,使得它们与  x  轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明: 你不能倾斜容器。 示例 1: 示例 2: 这道

    2024年01月19日
    浏览(60)
  • 【算法专题】双指针—盛最多水的容器

      分析这个题目不难得出一个 容积公式   解法一:暴力枚举(超时) 套用上述的容积公式,使用 两个for循环 来枚举出所有可能的情况,再挑出最大值即可,但是这种写法会超时,导致不通过。时间复杂度是O(n^2) 可以自己去尝试一下。  解法二:双指针  设两个指针 left,

    2024年02月06日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包