LeetCode 11. 盛最多水的容器

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