今天無意間發現了一道挺好玩的演算法題,它源自 Twitter 的一道面試題——「twitter puddles」,就來看看如何用 JavaScript 實現它。
先看一幅圖:

圖中的數字是根據一個陣列的內容而來,每個數字模擬一道牆的高度,最後生成一面牆。問題是:當下雨時,這面牆能裝多少水?以 1 為計數單位。
下面是裝完水之後的樣子:

看完圖會發現它其實很好玩。原理也不複雜,主要有兩個要點:
/**
* 計算以陣列項為高度的牆能裝多少水
* 陣列例子 [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;
// 以左右兩邊最大值內小的為准
// 假如當前值大於或者等於這個值什麼都不做
if(arg[i] < min){
count += min - arg[i];
}
}
console.log(count);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11
程式邏輯是:對每個位置(排除首尾),分別找出它左側與右側的最大值,取兩者中較小者作為水位上限;若該位置本身高度低於這個上限,就能裝「上限減自身高度」這麼多的水,累加起來即為總水量。
實現起來是不是挺簡單的?其實只要願意動腦,用 JavaScript 能實現很多好玩的東西。這道題也提醒我們:先把問題拆解成清晰的子規則,程式碼自然水到渠成。