今天發(fā)現(xiàn)了一個挺好玩的算法題,下面是它的算法描述,源自twitter的一道面試題。
twitter puddles 算法描述
先看一副圖
上圖里的數(shù)字是根據(jù)一個數(shù)組內(nèi)容來描述的,最后會根據(jù)每個數(shù)字的大小來模擬一道墻的高度,最后生成一面墻,問你,當(dāng)下雨的時候,這面墻可以裝多少水,以1為計數(shù)單位。
下面是裝完水之后的一面墻的樣子
看完上面上幅圖,感覺是不是很好玩,確實,下面來簡單的分析下它的算法實現(xiàn)
其實這個原理比較簡單,總共有下面幾個要點:
1.最左邊和最右邊肯定不能裝水
2.裝水的高度依賴自身左右兩側(cè)內(nèi)兩個最大值其中的最小值
下面我們用js來簡單的實現(xiàn)它：
/**
* 計算以數(shù)組項為高度的墻能裝多少水
* 數(shù)組例子 [2,5,1,2,3,4,7,7,6,9]
**/
function getWaterCounts(arg){
var i = 0,
j = 0,
count = 0;
// 第一項和最后一項都得排除
for(i = 1; i < arg.length - 1; i++){
var left = Math.max.apply(null, arg.slice(0, i + 1));
var right = Math.max.apply(null, arg.slice(i, arg.length));
var min = left >= right ? right : left;
// 以左右兩邊最大值內(nèi)小的為準(zhǔn)
// 假如當(dāng)前值大于或者等于這個值什么都不做
if(arg[i] < min){
count += min - arg[i];
}
}
console.log(count);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11
總結(jié)
嘿嘿,實現(xiàn)是不是挺簡單的,其實只要你愿意思考,用js可以實現(xiàn)很多好玩的東西.
