前言
这道面试题是我在博客园首页的一篇文章中看到的，面试题我简单的提取出来了，文章链接:http://news.cnblogs.com/n/192014/。
在我用JS实现了我自己的想法之后，我再一次看了这篇文章。在这篇文章的评论里，我惊喜的发现，有些大牛给出了更好的思路，
我会备注在这篇文章的后面，也可以直接去看原文的评论。博客园大牛还是很多的，程序猿是很聪明的群体。:):)
面试题
一个平面上有很多墙,高度参差不齐,每堵墙平行挨着,如下图所示,
计算如下所示的图墙可装水量，框里面的数字代表墙的高度
具体实现
1.可以先试着思考下怎么做:)
2.用JS实现的
/**
* 思路:
* 1.确定可装水的区域
* 区域满足如下条件才可装水:
* a. 必须包含至少三堵墙
* b. 最左(右)侧的墙的高度必须小于另外一侧
* c. 非最外侧的墙的高度一定小于或者等于最外侧墙中最小的高度的墙
* 2.计算可装水区域内某堵墙可装水的容积volume
* 3.计算可装水区域内所有墙可装水容积之和
* 4.计算所有可装水区域容积之和
*
* 实现:
* 1 找出最高墙的位置 iMaxIdx
* 2 从左至右计算可装水容积 V1 直至第iMaxIdx堵墙
* 3 从右至左计算可装水容积 V2 直至第iMaxIdx堵墙
* 4 总的可装水容积:V1+V2
*/
var aWallH = [2,5,1,2,3,4,7,7,6]; //所有墙的高度
var iWallW = 1; //墙宽度
var iWallL = 1; //墙长度
var iTotalV = 0; //总可装水容积
var iMaxWallIdx = 0; //最高墙的位置
var getMaxIdx = function(aO){ //找出最高墙的位置
var iMax = 0,iIdx = 0;
for (var i = 0; i < aO.length; i++){
if (iMax < aO[i]){
iMax = aO[i];
iIdx = i;
}
}
return iIdx;
};
var calVolume = function(aO,start,end,x,w,l){ //计算可装水容积
var iLeftH = 0;
var iAreaV = 0;
var iTotalV = 0;
var i = start;
for (; (x == 1) ? (i <= end) : (i >= end); i = i + x){
if (iLeftH < aO[i]){
iLeftH = aO[i];
} else {
break;
}
}
for (; (x == 1) ? (i <= end) : (i >= end); i = i + x){
if (iLeftH > aO[i]){
iAreaV += (iLeftH - aO[i]) * w * l;
} else {
iLeftH = aO[i];
iTotalV += iAreaV;
iAreaV = 0;
}
}
return iTotalV;
}
iMaxWallIdx = getMaxIdx(aWallH);
iTotalV += calVolume(aWallH,0,iMaxWallIdx,1,iWallW,iWallL);
iTotalV += calVolume(aWallH,aWallH.length-1,iMaxWallIdx,-1,iWallW,iWallL);
console.log(iTotalV);
博客园大牛给出的更好的思路
还是折叠吧:):)
/*
* 第7楼osold发表于 2013-11-01 14:06
* 这个其实对应图形学里面的一个扫描线填充算法。
*用那个算法实现比较简单。
*/ /*
*
备注：此方法有问题！ 第12楼Kalou发表于 2013-11-01 17:12
*将n个点按顺序连接成折线，分别计算每2个点之间的高度差，
*当遇到第一个负数时，表示可能开始收集到水，与后面的数相加，
*知道大于0，此区间*代表能收集到水。依次类推。例如
*10块砖的高度分别为[2,5,1,3,1,2,1,7,7,6],
*此时他们之间的距离分别为 [+3,-4,+2,-2,+1,-1,+6,+0,-1],
*第一个负数为-4，代表5这里可能开始**收集到水，
*然后向下遍历，-4+2《=0，-4+2-2《=0，-4+2-*2+1《=0，-4+2-2+1-1《=0，-4+2-2+1-1+6》0，
*这里终止，代表*收集雨水区域为[5,1,3,1,3,1,7] */
后记
1. js功能很强并执行方便，所以我选择了JS实现。
2.思路都是相同的，用其他语言一样可以实现，这个看个人的喜好。
3.实现思路就可以称之为算法吧，不只局限排序 :)
4.有空多思考，多训练，否则长久下去，思维会变迟钝。