leetcode 11.盛最多水的容器(python)-蒲公英云

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

野性酷女 2022-05-14 05:52 279阅读 0赞

【前言】

       python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]
       github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

【正文】

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