11. 盛最多水的容器

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

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

解法一

自己没看答案前自己的做法，也是很多人最容易想到的做法，就是分别列举出所有可能的容器并且比较大小，但是时间复杂度是O(n^2)，没有通过力扣的时间要求。

def maxArea1(height):
    """超出时间限制"""
    n = len(height)
    s = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            t = min(height[i], height[j]) * (j - i)
            if t > s:
                s = t
    return s

解法二

参考力扣官方答案，就是采用双指针的做法，用左右指针分别指向数组的两边，然后逐步的往中间移动指针，每次移动值小的那边的指针，因为只有这样后面的装的水才有可能最多。

自己之前也想到了用双指针，也相到了从左右往中间移动，但是不知道怎么移动指针，以后还是要多观察尝试，记住满足某个条件才移动指针，左右指针也没必要同时移动。

def maxArea2(height):

    l, r = 0, len(height) - 1  # 左右两个指针，从两头往中间移动
    ans = 0  # 记录面积
    while l < r:
        area = min(height[l], height[r]) * (r - l)
        # 比较记录最大的面积
        ans = max(ans, area)
        # 如果左边的值比右边的小就移动左边的指针
        if height[l] < height[r]:
            l += 1
        # 反之，如果右边的值不比左边的大，就移动右边的指针
        else:
            r -= 1
    return ans

复杂度分析

• 时间复杂度：O(N)，双指针总计最多遍历整个数组一次。
• 空间复杂度：O(1)，只需要额外的常数级别的空间。

力扣官方答案