本文详细解析源自Twitter的一道经典面试题：Puddles算法。通过JavaScript代码实现，讲解如何利用数组模拟墙体高度，计算降雨后的总蓄水量。核心逻辑在于遍历数组，取当前元素左右两侧最大值中的较小值作为水位高度，累加差值得到最终结果。
Twitter Puddles算法背景与原理
近期研究到一个有趣的算法问题，该题目源自Twitter的一道技术面试题。
关于Twitter Puddles算法的具体描述如下。
首先参考一张示意图。
图中的数字对应一个数组元素，每个数值代表模拟墙体的高度，从而构建出一面墙。问题在于：当这面墙遇到降雨时，能够容纳多少单位的水？
下图展示了蓄水完成后的墙体状态。
观察上述图像后，可以发现其趣味性，接下来简要分析该算法的实现思路。
该算法原理相对直观，主要包含以下关键点：
1. 墙体最左侧和最右侧的边缘无法蓄水。 2. 当前位置的蓄水高度取决于其左侧和右侧墙体内最大高度的较小值。
JavaScript代码实现
接下来使用JavaScript语言进行具体实现。
具体代码实现如下：
/**
* 计算以数组项为高度的墙能装多少水
* 数组例子 [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可以解决许多有趣的问题。