leetcode力扣第11题：盛最多水的容器（算法题中等难度）

题目描述：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例1：

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

示例 2：

输入：height = [1,1]
输出：1

解题思路：

首先由题意可知，容器的水位高度由左壁（假设坐标索引为i）和右壁（假设坐标索引为j）之中较矮的那一个决定。可得到容器存储水量的计算公式为：area = min(height[i],height[j])*(j-i)。然后是要找到一个方法，求出所有area中的最大值。如果通过两个for循环暴力求解，当height数组中元素个数急剧上升时，算法时间开销会非常大。

通过观察可以发现：当初始容器左右壁坐标索引分别为0、len(height)-1时，假设height[0]<height[len(height)-1]，即容器左壁更矮，若从左壁开始收缩，寻找下一个容器左壁（坐标索引为i+1），新的面积可能增大（当height[i]<height[i+1]），也可能减小（当height[i]>height[i+1]），也可能不变（当height[i]==height[i+1]）。而若从左壁开始收缩，寻找下一个容器右壁（坐标索引为j-1），那么新的面积只可能不变（当height[i]<=height[j-1]）或减少（当height[i]>height[j-1]）。

所以从容器左右壁中，高的那一侧开始收缩是没有意义的。应该从矮的一侧移动寻找下一个容器。当i>=j时，循环结束。

代码：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i,j,max_area = 0, len(height) - 1, 0
        while i < j:
            max_area = max(max_area, min(height[i],height[j])*(j-i))
            if height[i] <= height[j]:
                i += 1
            else:
                j -= 1
        return max_area