美文网首页工作生活
LeetCode 11. 盛最多水的容器

LeetCode 11. 盛最多水的容器

作者: liulei_ahu | 来源:发表于2019-07-03 10:54 被阅读0次

    11. 盛最多水的容器

    给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。


    示例:

    图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49

    解题思路

    • 暴力穷举法
    class Solution:
        def maxArea(self, height: List[int]) -> int:
            maxarea = 0
            for l in range(len(height)):
                if height[l]*(len(height)-1-l) < maxarea:
                    continue
                for r in range(l+1,len(height)):
                    maxarea = max(maxarea, min(height[l],height[r])*(r-l))
            return maxarea
    #这种方法我提交一直显示超时,没有想到更好的优化方法,如果读者有谁想到欢迎在评论里面指出。
    
    • 容器面积的height受最短边的影响,开始从最外围开始遍历,然后逐步从短边到长边遍历,保存每次遍历围成的矩阵的面积即可
    class Solution:
        def maxArea(self, height: List[int]) -> int:
            l = 0
            r = len(height)-1
            maxarea = 0
            while(l<r):
                maxarea = max(maxarea,min(height[l],height[r])*(r-l))
                if height[l]<height[r]:
                    l+=1
                else:
                    r-=1
            return maxarea
    

    相关文章

      网友评论

        本文标题:LeetCode 11. 盛最多水的容器

        本文链接:https://www.haomeiwen.com/subject/deafhctx.html