11. 盛最多水的容器

方法 1：双指针

思路

l 和 r 形成了一个接雨水的区域，那么要想找到更大的区域，需要在 l 和 r 中间再找一条边构成新的区域进行比较，即在 l 和 r 中选择一条进行移动。
需要移动 l 和 r 中较小的那个，反证法证明如下：假设 l 较大，若移动 l：

3. 因此，我们只需要不断移动小的那个指针，返回这个过程中最大的面积即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l, r = 0, n - 1
        ans = 0

        while l < r:
            area = min(height[l], height[r]) * (r - l)
            ans = max(area, ans)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

复杂度

时间复杂度：O(n)
空间复杂度：O(1)