目录

问题

思路

代码

---

问题

给你 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)。这肯定是不行的，于是我们需要找找规律。

就拿上面那个图为例子，我们假设有两个指针，指向头和尾，现在要移动一个柱子，我们要移动哪一根，移动指向长的还是短的的指针？

那肯定是要移动指向短的那根的指针，因为，这个面积是   短的柱子长度*两个柱子的距离。我们如果移动指向长的那根的指针，两个柱子的距离变短了不说，最短的那根柱子长度只有可能不变或者更短。

于是，只有移动指向短的那根柱子的指针，才有可能使得面积变大，于是，经过分析和双指针的引入，时间复杂度从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;
};