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.
- 題目大意
給定一組正整數(shù)a1...an, 代表了坐標(biāo)系中(i,ai), 對(duì)于每個(gè)點(diǎn)，有一條垂直到x軸的線段，找到兩條線和x軸組成一個(gè)容器馏艾，是它可以裝最多的水击纬。
題目讀起來(lái)有點(diǎn)暈煌珊，配上一張圖可能會(huì)好一點(diǎn)：
如上圖所示芍躏，對(duì)應(yīng)的a1...an=[5,3,7,8,6,1], 而最大的容器是藍(lán)色的區(qū)域屯阀，可以裝的水maxArea= 5*4=20
算法1：枚舉每?jī)蓷l線段固灵，找到最大值捅伤，時(shí)間效率O(n2) ,當(dāng)n非常大的時(shí)候很容易超時(shí)。
算法2：觀察這個(gè)容器巫玻，可以發(fā)現(xiàn)其實(shí)容器的最大容量只和兩邊中的最短邊有關(guān)（類似與短板理論）.丛忆。所以我們可以設(shè)置兩個(gè)指針祠汇，剛開始指向最兩頭的兩邊；我們向中間移動(dòng)其中較短邊的指針（因?yàn)橐苿?dòng)的時(shí)候距離兩邊之間的距離變短了熄诡，只有兩邊中的短邊 變長(zhǎng)的時(shí)候可很， 才有可能得到更大的容量。如果我們移動(dòng)長(zhǎng)邊的指針凰浮， 總?cè)萘窟€是會(huì)取決于短邊根穷，但距離變短了，容量一定更小导坟。） 重復(fù)這個(gè)步驟屿良，直到最后兩條邊。
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxArea=0;
let length;
while ((length=height.length)>1){ //當(dāng)剩余的線段大于1的時(shí)候繼續(xù)
maxArea=Math.max(maxArea,Math.min(height[0],height[length-1])*(length-1));
if (height[0]<height[length-1]){ 較短的那頭向中間移一個(gè)
height.shift();
}else{
height.pop();
}
}
return maxArea;
};
