leetcode #11 Container With Most

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

• 题目大意
  给定一组正整数a1...an, 代表了坐标系中(i,ai), 对于每个点，有一条垂直到x轴的线段，找到两条线和x轴组成一个容器，是它可以装最多的水。

题目读起来有点晕，配上一张图可能会好一点：

如上图所示，对应的a1...an=[5,3,7,8,6,1], 而最大的容器是蓝色的区域，可以装的水maxArea= 5*4=20

算法1：枚举每两条线段，找到最大值，时间效率O(n²) ,当n非常大的时候很容易超时。
算法2：观察这个容器，可以发现其实容器的最大容量只和两边中的最短边有关（类似与短板理论）.。所以我们可以设置两个指针，刚开始指向最两头的两边；我们向中间移动其中较短边的指针（因为移动的时候距离两边之间的距离变短了，只有两边中的短边 变长的时候， 才有可能得到更大的容量。如果我们移动长边的指针， 总容量还是会取决于短边，但距离变短了，容量一定更小。） 重复这个步骤，直到最后两条边。

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let maxArea=0;
    let length;
    while ((length=height.length)>1){ //当剩余的线段大于1的时候继续
        maxArea=Math.max(maxArea,Math.min(height[0],height[length-1])*(length-1));
        if (height[0]<height[length-1]){ 较短的那头向中间移一个
            height.shift();
        }else{
            height.pop();
        }
    }
    return maxArea;
};