【力扣算法12】之 11. 盛最多水的容器 python

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

问题描述

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题

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

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题

示例1

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题

输入:[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

思路分析

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题

  1. 首先,我们定义了一个Solution类,其中包含解决问题的方法maxArea。
  2. 方法maxArea接收一个整数数组height作为参数。
  3. 我们通过双指针来解决这个问题。左指针left初始化为数组的第一个元素下标0,右指针right初始化为数组最后一个元素的下标n-1。
  4. 初始化最大面积max_area为0。
  5. 进入循环,条件是左指针小于右指针。这是因为当左指针和右指针相遇时,无法再构成有效的容器。
  6. 在每一次循环中,我们计算当前的面积curr_area。面积的计算公式是两个指针所指高度较小值乘以两个指针之间的距离即(right - left)。
  7. 更新最大面积max_area,通过将当前面积curr_area与max_area比较,如果curr_area更大,则更新max_area。
  8. 接下来,根据以下三种情况移动指针:
    • 如果height[left]小于height[right],那么我们将左指针left向右移动一位,即left += 1,因为移动左指针不能增加当前的面积。
    • 如果height[left]大于height[right],那么我们将右指针right向左移动一位,即right -= 1,因为移动右指针不能增加当前的面积。
    • 如果height[left]等于height[right],那么我们既可以移动左指针也可以移动右指针。在这种情况下,无论移动哪个指针,都不会改变当前的面积。
  9. 循环结束后,返回最大面积max_area作为结果。

这种解决方法的核心思想是通过不断缩小有效宽度的范围,来寻找容器的最大面积。通过比较较小高度的指针向内移动,可以保留更有可能得到更大面积的高度。最终,我们得到了两条垂线所形成容器的最大面积。

代码分析

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题

  1. 首先,我们定义了一个Solution类。
  2. 在类中,我们定义了一个方法maxArea,它接收一个整数数组height作为参数。
  3. 我们首先获取数组height的长度n,用于后续循环的条件判断。
  4. 初始化左指针left为0,右指针right为数组最后一个元素的下标n-1。
  5. 初始化最大面积max_area为0。
  6. 进入循环,条件是左指针left小于右指针right。
  7. 在循环中,我们计算当前的面积curr_area,即两个指针所指高度较小值乘以两个指针之间的距离,使用min()函数取得较小值。
  8. 更新最大面积max_area,通过将当前面积curr_area与max_area比较,并将较大值赋给max_area,用max()函数实现。
  9. 接下来,使用三个判断条件来决定指针的移动:
    • 如果height[left]小于height[right],说明左指针指向的高度较低,移动左指针left向右移动一位,即left += 1。
    • 如果height[left]大于height[right],说明右指针指向的高度较低,移动右指针right向左移动一位,即right -= 1。
    • 如果height[left]等于height[right],说明两边的高度相等,无论左指针left还是右指针right都可以移动,所以同时将左指针left向右移动一位,即left += 1,右指针right向左移动一位,即right -= 1。
  10. 循环结束后,返回最大面积max_area作为结果。

完整代码

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题

class Solution(object):
    def maxArea(self, height):
        n = len(height)  # 获取数组height的长度n
        left, right = 0, n - 1  # 初始化左指针left为0,右指针right为数组最后一个元素的下标n-1
        max_area = 0  # 初始化最大面积max_area为0

        while left < right:  # 进入循环,条件是左指针left小于右指针right
            curr_area = min(height[left], height[right]) * (right - left)  # 计算当前的面积curr_area,即两个指针所指高度较小值乘以两个指针之间的距离
            max_area = max(max_area, curr_area)  # 更新最大面积max_area,通过将当前面积curr_area与max_area比较,并将较大值赋给max_area

            if height[left] < height[right]:  # 如果height[left]小于height[right]
                left += 1  # 移动左指针left向右移动一位
            elif height[left] > height[right]:  # 如果height[left]大于height[right]
                right -= 1  # 移动右指针right向左移动一位
            else:  # 如果height[left]等于height[right]
                left += 1  # 同时移动左指针left向右移动一位
                right -= 1  # 同时移动右指针right向左移动一位
        
        return max_area  # 返回最大面积max_area作为结果

详细分析

  1. 首先定义一个名为Solution的类。
class Solution(object):
  1. 然后,我们在Solution类中定义了一个名为maxArea的方法,该方法接收一个名为height的参数。
    def maxArea(self, height):
  1. 在方法体内部,我们获取数组height的长度,并将结果赋给变量n。
        n = len(height)
  1. 接下来,我们初始化左指针left为0,右指针right为数组最后一个元素的下标n-1。
        left, right = 0, n - 1
  1. 我们还定义了一个变量max_area,并将其初始化为0,用于保存最大面积的值。
        max_area = 0
  1. 在接下来的while循环中,我们判断左指针是否小于右指针,如果是,则执行循环体内的代码。
        while left < right:
  1. 在循环体内部,我们首先计算当前的面积curr_area,即两个指针所指高度较小值乘以两个指针之间的距离。
            curr_area = min(height[left], height[right]) * (right - left)
  1. 接着,我们更新最大面积max_area,通过将当前面积curr_area与max_area比较,并将较大值赋给max_area。
            max_area = max(max_area, curr_area)
  1. 然后,我们根据左指针和右指针指向的高度来移动指针。
  • 如果左指针指向的高度小于右指针指向的高度,则将左指针向右移动一位。
            if height[left] < height[right]:
                left += 1
  • 如果左指针指向的高度大于右指针指向的高度,则将右指针向左移动一位。
            elif height[left] > height[right]:
                right -= 1
  • 如果左指针指向的高度等于右指针指向的高度,则同时将左指针向右移动一位,并将右指针向左移动一位。
            else:
                left += 1
                right -= 1
  1. 循环结束后,我们返回最大面积max_area作为结果。
        return max_area

运行效果截图

调用示例

solution = Solution()
x = [1,8,6,2,5,4,8,3,7]
x1 = [1,1]
print(solution.maxArea(x))
print(solution.maxArea(x1))

运行结果

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题

完结

【力扣算法12】之 11. 盛最多水的容器 python,python案例分析归纳,算法,leetcode,python,双指针,最大面积,容器问题,python面试题文章来源地址https://www.toymoban.com/news/detail-562378.html

到了这里,关于【力扣算法12】之 11. 盛最多水的容器 python的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 力扣-盛最多水的容器

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

    2024年01月15日
    浏览(41)
  • 【算法专题--双指针算法】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月20日
    浏览(58)
  • leetcode 11. 盛最多水的容器

    leetcode 11. 盛最多水的容器 解题思路 :双指针 每次向内移动矮的指针,因为如果向内移动高的指针,面积一定会变小;如果向内移动矮的指针,面积还有可能变大。

    2024年02月06日
    浏览(44)
  • 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日
    浏览(35)
  • LeetCode_11. 盛最多水的容器

    11. 盛最多水的容器 - 力扣(LeetCode) https://leetcode.cn/problems/container-with-most-water/         这题就是典型的是一道很经典的面试题,最优的解法是双指针,但很多人在第一次看到这题的时候很难想到用双指针来解(比如我)。好了,话不多说上解法: 首先我们设两个left和righ

    2024年02月14日
    浏览(39)
  • LeetCode_11_中等_盛最多水的容器

    给定一个长度为 n n n 的整数数组 h e i g h t height h e i g h t 。有 n n n 条垂线,第 i i i 条线的两个端点是 ( i , 0 ) (i, 0) ( i , 0 ) 和 ( i , h e i g h t [ i ] ) (i, height[i]) ( i , h e i g h t [ i ]) 。 找出其中的两条线,使得它们与 x x x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的

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

    给定一个长度为  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)
  • 【算法】双指针求解盛最多水的容器

    Problem: 11. 盛最多水的容器 首先我们来解析一下本题 题目中说到,要找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水 。 那我们现在来看最外侧的两根,一个高度为8,一个则为7,那我们肯定选择高度为7的, 如果选择8的话就会出现溢出的问题 ;我们这

    2024年02月11日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包