题目
给定 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。
示例
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解答
方案1：暴力求解
我们考虑所有的容器组合，用两个指针——左指针（left）和右指针（right）标记容器两壁的位置，计算每个容器所对应的容积并更新最大值。
class Solution:
def maxArea(self, height):
max_area = 0
for right in range(1, len(height)):
for left in range(right):
cur_area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, cur_area)
return max_area
方案2：向中靠拢
容器的容积与底面积（这里我们把两个板之间的距离称为底面积）有关，而且在底面积固定的情况下，短板效应决定了容器的容积取决于长度较低的板。
我们定义左右两个指针，左指针（left）和右指针（right）的初始位置在数组（height）两端的位置，此时相当于容器的底面积最大，然后比较两指针对应的板的高度，高度较低的指针向另一个指针方向移动一个单位距离，记录下每次的最大容积，直到两者相遇为止。
这里的逻辑是，左指针右移一个单位或者右指针左移一个单位后，两个指针的距离是一样的，相当于容器的底面积是一样的，在这样的情况下我们就要考虑如何能保证移动指针后的短板尽可能最长，两指针向中间移动相当于换掉一个板，如果去除短板保留长板相比于去除长板保留短板，更有可能使容器的面积增大。
以上是直观理解，需要严格数学推导。。。
class Solution:
def maxArea(self, height):
left, right, max_area = 0, len(height)-1, 0 # 从两端开始，左右指针向中间走
while left < right:
current_area = min(height[left], height[right]) * (right-left)
max_area = max(max_area, current_area)
if height[left] > height[right]:
right -= 1
else:
left += 1
return max_area
如有疑问或建议，欢迎评论区留言~
