JavaScript實作twitter puddles演算法實例_javascript技巧

今天發現了一個挺好玩的演算法題,下面是它的演算法描述,源自twitter的一道面試題。

twitter puddles 演算法描述

先看一副圖

上圖裡的數字是根據一個數組內容來描述的,最後會根據每個數字的大小來模擬一道牆的高度,最後生成一面牆,問你,當下雨的時候,這面牆可以裝多少水,以1為計數單位。

下面是裝完水之後的一面牆的樣子

看完上面上幅圖,感覺是不是很好玩,確實,下面來簡單的分析下它的演算法實現

其實這個原理比較簡單,總共有下面幾個要點:

1.最左邊、最右邊一定不能裝水
2.裝水的高度依賴自身左右兩側內兩個最大值其中的最小值

下面我們用js來簡單的實作它：

複製程式碼 程式碼如下:

/**
*  計算以陣列項為高度的牆能裝多少水
*  陣列範例 [2,5,1,2,3,4,7,7,6,9]
**/
function getWaterCounts(arg){
    var i = 0,
        j = 0,
        count = 0;
    // 第一項和最後一項都要排除
    for(i = 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]             count = min - arg[i];
        }
    }
    console.log(count);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

總結

嘿嘿,實現是不是挺簡單的,其實只要你願意思考,用js可以實現很多好玩的東西.