【lc刷题】11 盛最多水的容器_Day07(21/300)

21/300

11. 盛最多水的容器
    给定 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

如果暴力都算的话，费时。思考这道题的特点，为了达到最大化，甭管长短，俩人距离要越远越好，面积=此距离*min(俩人)。

假设左人是小的，让左人不动，右人往里走，距离往里缩，即使新右人更大，我们也只要min(俩人)，更别提距离也小了，所得到的面积永远比最早得到的小，所以不能这么动；

所以当左人是小的，右人不动，让左人往里走，同理当右人是小的，左人不动，让右人往里走。也就是谁小谁动～

双指针法：

• 时间复杂度：O(n)，一次扫描。
• 空间复杂度：O(1)，使用恒定的空间。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height) - 1
        _area = 0
        
        while l < r:
            area = min(height[l],height[r]) * (r - l)
            if _area < area:
                _area = area
                
            #move r or l:
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return _area

今天复习日，就刷一道。