来自:http://blog.jobbole.com/50705/
看下面这个图片”
“在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表，数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]”
“假如开始下雨了，那么墙之间的水坑能够装多少水呢？”
“以1×1的方块为单位计算容积。所以，在上边的图中下标为1以左的都会漏掉。下标7以右的也会漏掉。剩下的只有在1和6之间的一坑水，容积是10”
---------------------------------------------------------------
我大概用了30分钟想到了解法,但是翻译成可执行代码用了大半天.
原因一是我的思维过程其实包含了大量的默认判断,对于人脑很自然,但是对于机器就得一一明确指出.
二是我一开始设计了个复杂的数据结构,导致测试过程中的索引让我头脑混乱.后来肉眼观察代码的字符规律,发现完全可以用一个简单的数组代替...肉眼发起的优化啊= =..
为什么会犯这种错误,因为一开始我有种多多益善的倾向,把衍生数据和原始数据都放到一个元组里面吧,万一哪个地方所有数据都需要呢?
下面是我的解法.思路是先将这些墙按其高度从高到低排列形成一个新表arr2,arr2的数据本身不是高度,而是这个高度在arr中的索引.然后再遍历arr2,检查两墙之间能累积多少水.
代码:
arr=[2, 5, 1, 2, 3, 4, 7, 7, 6] def waterWall(arr):
#print arr
#print arr2
#[2, 5, 1, 2, 3, 4, 7, 7, 6]
#[7, 6, 8, 1, 5, 4, 3, 0, 2] def calWater(big,sml):
#根据传入的2个墙的索引值计算它们之间的水容量
#水容量是由较矮的墙决定的
shorter=min(arr[sml],arr[big])
return sum((shorter-mid for mid in arr[sml+1:big]))
#按墙高倒序排列的索引值数组,最左边的成员表示最高的墙的索引值,以此类推
arr2=map(lambda x:x[1],
sorted(((k,i) for i,k in enumerate(arr)),
reverse=1))
#已检查的区域,用于控制计算以及退出循环
ckdRange=[]
#总水量
waterVol=0 end=len(arr2)-1 #首次循环是计算2个成员,以便初始化区域
#之后的循环将成员sml和ckdRange的上下界比较
for i in range(end):
big,sml=arr2[i],arr2[i+1]
#如果是首次循环,那么初始化ckdRange和水量
if not ckdRange:
#墙更高不一定索引更大,保证sml指代较小数,简化判断
if sml>big:
sml,big=big,sml
#传入两墙的索引,开始累积水量
waterVol+=calWater(big,sml)
#初始化已检查的区域
ckdRange.extend([sml,big])
elif sml>ckdRange[1]:
waterVol+=calWater(sml,ckdRange[1])
ckdRange[1]=sml
elif sml<ckdRange[0]:
waterVol+=calWater(ckdRange[0],sml)
ckdRange[0]=sml
#如果区域已经覆盖全部成员,那么退出循环
#最极端的情况是arr首尾成员是最高墙时,只需迭代一次就退出 #print 'range checked:',ckdRange,'water:',waterVol
if ckdRange==[0,end]:
break
#返回最终水量
return waterVol print waterWall(arr)