這個題目來自 Twitter 的面試題,看起來只是幾何圖形,實際考驗的是對「邊界約束」的抽象能力,蠻有意思。
先看下面這張圖:

圖中的數字來自一個陣列,每個數字對應一道牆的高度,組合起來就形成一面高低起伏的牆。問題是:下雨時,這面牆最多能承接多少單位的水?
換成注水之後的樣子如下:

原理其實不難,掌握兩點即可:
1. 最左側與最右側的格子一定存不了水,因為沒有邊界可擋。
2. 某個位置能蓄到的高度,取決於它左右兩側各自最大值中的「較小者」——木桶效應,短板決定水位。
/**
* 計算以陣列項為高度的牆能裝多少水
* 陣列例子 [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
這裡的 min - arg[i] 就是該格能承接的水量,若本身高度已達或超過水位則略過。這個版本勝在直白好懂,缺點是每個位置都要 slice 兩次求最大值,時間複雜度為 O(n²)。若資料量龐大,可以改用「預先由左向右、由右向左各掃一次,記下每格的左右最大值」的做法,把複雜度壓到 O(n)。
演算法的樂趣就在這裡:題目聽起來抽象,一旦把「短板決定水位」這個直覺寫成程式,答案便自然浮現。只要願意動腦,JavaScript 能玩出很多有趣的東西。