【LeetCode】盛最多水的容器（JS实现）

问题

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

思路

第一反应，暴力破解，把所有的可能算一遍，时间复杂度是O(n2)。这肯定是不行的，于是我们需要找找规律。

我们现在有两个指针，分别指向第一根和最后一根。

假设  第一根高度是  H1，最后一根高度是Hn，H1大于Hn，所以他们围出来的面积是多少呢？

Hn*（n-1）。

现在我们要让其中一根指针向里移动，还要面积有可能上升。我们思考，面积取决于两根柱子的距离和两根柱子中最短的一根。现在，我们向里移动，两个指针指向的柱子的相对距离变短了，我们为了面积上升，只能选择让 两根柱子中较短的那一根长度较长，于是，我们要移动指向较短的柱子的那一个指针。

循环上述操作，两个指针相遇时结束循环，完成遍历。

于是，经过分析和双指针的引入，时间复杂度从O(n2)变成了O(n)

代码

var maxArea = function(height) {
    let frontPoint = 0;
    let endPoint = height.length - 1;
    let max = 0;
    while (frontPoint < endPoint) {
        max = Math.max(max, (endPoint - frontPoint) * (height[frontPoint] > height[endPoint] ? height[endPoint--]: height[frontPoint++]))
    }
    return max;
};

​