题目：

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

示例二：

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

示例三：

输入：height = [4,3,2,1,4]
输出：16

示例四：

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

提示：

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

思路

在做这道题的时候，我没想到用双指针的方法，而是用复杂度为 O(n^2) 的嵌套循环暴力破解的方法，结果提交之后跑测试用例超时了。当时的想要解决的问题是如何记住面积最大的两个高度值的位置。结果思路是错误的。

这道题目的关键在于对面积公式的理解，两条高围成一个容器，能装的水的面积是由两条高之间的距离和那条最小高来决定的。假设左边的高度在数组中的下标为 x，右边的高度在数组中的下标为 y，那么能装水的面积就是：s = min(height[x], height[y]) * (y - x) 。

将公式分为两个部分，一个是 min(height[x], height[y])，一个是 y - x。height 是题目中给定的数组，所以我们只要改变或者 x，y 就可以获得一个新的 s。我们将这个每次迭代得到一个新的 s 都会将其与当前的 s 对比，保留较大值。

因为数组中的高度是随机的，所以无论每次移动哪个指针 min(height[x], height[y]) 的值的变化都是不确定的，而 y - x 的变化是更好控制的，我们可以将两个指针初始化在数组的两端，左指针只能向右移动，而右指针只能向左移动。这样就可以保证 y - x 是随着每次指针移动递减的。

我们遍历的目的是得到一个最大的 s，因为 y - x 是每次指针移动都会减小的。那每次移动的结果都要保证 min(height[x], height[y]) 是有可能大于当前的值的。由于 min 是计算最小值，所以改变更小的数字可能让 min(height[x], height[y]) 的值变大，而改变当前更大的数字只会使其更小或者不变，所以要移动指向更小数字的指针。

要点

• 从数组的两端设置双指针。
• 每端的指针只能向另一端移动，每次只能移动一个位置。
• 每移动一次指针，就会有一个新的可能的结果。
• 只有每次移动指向更小的数字的指针，才有可能得到更大的结果。

代码

function maxArea(height: number[]): number {
    let [max, left, right] = [0, 0, height.length -1];
    while(left !== right){
        max = Math.max(max, (right - left) * Math.min(height[left], height[right]))
        if(height[left] < height[right] ){    
            left = left + 1
        } else {
            right = right - 1
        }
    }
    return max;
};

相关阅读

• 11. 盛最多水的容器 - 力扣（LeetCode） (leetcode-cn.com)