[LeetCode]Trapping Rain Water

求求你们快狂点这里看代码吧!!

这个题蛮有意思的,就是给你几个柱子,每个柱子占地1个单位长度,柱子高为0的话代表这个单位没有柱子,问你,当一天下大雨的时候,这些柱子可以围起来多少水?请参考题目里给出的图片(点这里)。

做法是用一个栈维护高度递减的柱子序列,并记录这些柱子所占的长度(后期会有更新柱子长度,不再一直是1)。具体做法是这样:

1.当碰到的柱子比栈首的柱子要矮时,把这根柱子入栈,并记录长度为1。

2.否则,计算栈首柱子T与该柱子L高度的差距,并乘以T柱子的长度,此为T柱子的水位上升到L时能够装的水量,把这个水量加到总水量当中。然后弹出T柱子,继续比较栈首柱子和L柱子,直到遇到比L柱子高的柱子,或者发现栈内所有柱子都比L柱子矮(此时栈为空)。

3.当L柱子比栈内所有柱子都高时,计算栈底那根柱子B与L柱子高度的差距,并乘以B柱子的长度,此为要溢出的水,所以用总水量减去这个溢出的水量。

4.把L柱子加入到栈中,并记录长度。当这跟L柱子比栈内所有柱子都要高时(这时栈内所有元素都已弹出),记录长度为1。否则长度为弹出的所有柱子的长度之和再加1(以L柱子为水平面的水位所占的长度)。

本来可以画比较形象的图解释的,但是现在只会用画图软件,不会作那种图,大家不明白可以自己在草稿纸上画画,结合我的代码,手动走几步,基本就能明白了。



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*