(算法题)(python3)求盛水最多的容器大小

先上题干：

给定 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。

看到题目的第一眼，脑子里面浮现的是用暴力法：简单粗暴用两层循环来遍历每个元素，取高度相对较短一边的值为宽，乘以右侧元素下标减去左侧下标得到的长，最后将得到的面积依次比较，取其中最大的值即为结果。

方法在本地运行通过，于是放到leetcode上跑测试用例，但是在这里就出了问题，遇到样本比较大的测试数组，会因为运行时间比较长导致提交失败。。想想毕竟是中等算法题，如果还用简单粗暴效率低的老办法就没意思了，于是又有了下面的解法二。

解法二：

题目要求最大容器容量，容器的面积相当于是一个长方形的面积，即面积 = 长 * 宽，则基准条件是找出尽量大的长和宽。长对应的上图左右两根垂直线间距离，宽对应垂直线高度，这里要求两侧的柱子间距要尽量远，且两端高度要尽量高，代码如下：

def max_area(height):
    """
    :type height: List[int]
    :rtype: int
    """
    # 左右两侧下标
    left = 0
    right = len(height) - 1
    max = 0
    # 对比的数组元素至少有2个，则继续循环
    while right > left:
        l = right - left
        if height[left] < height[right]:
            h = height[left]
            sqr = h * l
            left = left + 1
        else:
            h = height[right]
            sqr = h * l
            right = right - 1
        if sqr > max:
            max = sqr
    return max

据官方的线索，这里的题解时间复杂度推荐是O(n)，即最多只能有一个循环，这里方法二的解法通过一个while循环判断得到结果，循环次数大致为数组的长度。