盛最多水的容器

给定一个长度为 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

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

双指针-从极限条件开始转变：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int right = height.size() - 1;
        int left= 0, mx = 0;
        while (left < right)
        {
            mx = max(mx, (right - left) * min(height[left], height[right]));
            if (height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return mx;
    }
};

首先这道题要求的值类似于面积，所以一定是要使用双指针分别指向容器两端的。然后我们再看到和这个面积有关的可变因素：左端点位置，右端点位置，容器高度（取左右两边中的较小值）。那么现在就有三个变量，然后高度是和左右端点位置关联的。如果我们每次循环固定一个端点的位置，很容易判断这样的时间复杂度是O(n²)。显然是不可行的，那么我们就不能固定端点位置，必须动态变化。

然后我们可以注意到其实左右端点的位置可以转换为容器的底座长度。而容器面积的大小同时取决于底座长度和高度。如果我们能控制其中一项为最大值，然后递减，那么变量就只有一个了。然后回到实际问题中，我们能控制的只有底座长度，因为这里的高度变化是不规律的，所以我们没法控制。但是我们可以让底座长度取最大值。

当底座长度取到最大值之后，想要让容器面积变大，就只能通过改变端点位置来改变高度了。而高度是由左右端点中高度低的那一端决定的，所以我们只有移动高度低的端点位置才可能改变高度。这时候底座长度一定会减小，但是高度可能会增加从而增加面积。那么怎么确定被我们移动的短板不会成为最优解的一个端点呢？

假设当前状态：[(left, right)]并且：[height[left] < height[right]]，即左边柱子的高度小于右边柱子的高度，因此左边是当前容器的短板。

根据双指针算法：

left++;

移动左指针，删除左侧柱子。

1. 当前面积

当前两个柱子构成的面积为：

[A=(right-left) * height[left]]

因为：[height[left]<height[right]]，所以当前容器的高度由：[height[left]]决定。

2. 分析被跳过的组合

左指针移动后，所有包含原左边柱子的组合都会被跳过。

这些组合形式为：[(left,k)]

其中：[k<right]，即右边选择的是当前右指针左侧的任意位置。

3. 计算被跳过组合的面积

对于任意：

[(left,k)]

其面积：

[A_k=(k-left) * min(height[left],height[k])]

由于：

[min(height[left],height[k]) <= height[left]]

所以：

[A_k <= (k-left) * height[left]]

4. 比较宽度

因为：

[k < right]

所以：

[k - left < right - left]

因此：

[(k-left) * height[left]<(right-left) * height[left]]

结合上面的不等式：

[A_k < (k-left) * height[left]]

得到：

[A_k<(right-left) * height[left]]

即：

[A_k < A]

5. 结论

对于当前状态：

[(left,right)]

如果：

[height[left]<height[right]]

那么：所有包含 left 的其他组合：

[(left,k),\ k<right]

都不可能获得比当前面积更大的结果。

因此：

left 不可能出现在最优解中，可以安全删除：

left++;

同理：

如果：

[height[left] > height[right]]

可以安全删除：

right--;