朋友面试字节跳动－头条的技术笔试水坑积水的问题。感觉很有趣。试着用自己的javascript知识提供一些解题算法思路。

有一组不同高度的台阶，由一个整数数组表示，数组中每个数是台阶的高度。当开始下雨了（足够多），台阶之间的水坑会积多少水呢？

如下图，可以表示为数组[0,1,0,2,1,0,1,3,2,1,2,1]，返回积水量6。

解题思路：

1　什么样的条件才能积水？

　　有凹的地方才能积水。

2　怎么判定凹？

　　左右凸起中间低即为凹。

3　只有两种状态是否可用二进制表示？

　　可以1凸0为凹，左右两边边界为凹时不考虑。

图例

以上图例，凹地分别是A，C，E，凸地分别是B，D

但A，E为边界，不能计为有效凹地

即此例中只有C能积水一个单位

如何计算台阶的高度影响

图例

B为整数3时，计算为1+1+1＝3，D为整数2时计算为1+1＝2

则可以将深度分别拆开计算

第一层：01010＝101统计为一个0

第二层：01010＝101统计为一个0

第三层：01000＝1统计为没有0

此图例中积水量等于2，

即第一层有效0的数量加第二层有效0的数量加第三层有效0的数量。

JS编码方案

将每一层的数据转成二进制，去掉边界无效的0，统计剩下的每一层0的数量，进行总和即为实际积水量。

<script language="javascript">
var ArrA=[0,1,0,2,1,0,1,3,2,1,2,1];//台阶的描述数组
var N=function (){
	var Result=0,aMax=Math.max.apply(Math,ArrA),ArrB;
	//Result:积水量的统计变量。aMax:台阶的最高值，ArrB:每层台阶转化1，0的临时存放数组。
	for(i=1;i<= aMax;i++)//循环每一层
		{
			ArrB=[];
	        for(x = 0; x < ArrA.length;x++)//循环每层所有的数并将其转化为0，1
			{
				if(ArrA[x] >= i) ArrB.push(1);
				else ArrB.push(0);
			}
			ArrB = ArrB.slice(ArrB.indexOf(1),ArrB.lastIndexOf(1)+1);//去掉左右边界无效的0。
			Result = Result+ArrB.join().split(0).length-1;//累加此层剩余有效0的数量
		}
		alert(Result);
	}();
</script>