leetcode 11.盛最多水的容器(python)

【前言】

python刷leetcode题解答目录索引：https://blog.csdn.net/weixin_40449300/article/details/89470836

【正文】

给定 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。

示例:

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

方法一：

两个for循环，暴力求解

方法二：

贪心算法：设置左右两个指针left 和 right，盛水容量由矮的高度决定，所以我们每次移动矮的高度。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0
        r = len(height)-1
        if not height or len(height) == 1 :
            return 0
        res = (r-l)*(height[l] if height[l] < height[r] else height[r])
        
        while l < r:
            if height[l] < height[r] :
                res = res if res > height[l]*(r-l) else height[l]*(r-l)
                l += 1
            else :
                res = res if res > height[r]*(r-l) else height[r]*(r-l) 
                r -=1
        return res

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_40449300/article/details/82355138
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-25 02:28:48
阅读 ( 968 )
分类：算法

leetcode 11.盛最多水的容器(python)

方法一：

方法二：

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看