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轴组成一个容器，是它可以装最多的水。
题目读起来有点晕，配上一张图可能会好一点：
image.png
如上图所示，对应的a1...an=[5,3,7,8,6,1], 而最大的容器是蓝色的区域，可以装的水maxArea= 5*4=20
算法1：枚举每两条线段，找到最大值，时间效率O(n2) ,当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;
};
