程序员面试题之“接雨水”

最近的大雨总是牵动着人们的心。

郑州的大雨淹了好多地方，上海因为台风而建议周一在家办公。作为一名软件工程师，没有技能去冲在第一线抗灾，那么我们就在大后方好好地修炼内功，提升自我吧。

今天我们就来看一道和“雨水”相关的题目。

题目

输入：[1,2,3,1,3]

输出：9

可以想象每一个数字是一个挡板，每个数字可保证大于0。

释义：样例中每一格可接的雨水分别为1，2，3，3，故输出为1+2+3+3 = 9

题目讨论

这道题目本身还是蛮有意思的，属于使用代码去模拟现实世界并解决其问题。这类题目首先要认真分析题目，多看一下例子，总结其规律，然后再解决即可。

我们以每一格为立足点，来看哪些因素会影响其接水量。

对于第一格来说，它的接水量是1，即左边的挡板高度为1，右边的挡板高度为2。因此可以得出结论：接水量取决于左右挡板中较矮的那一个。

对于现实世界，我们应该能比较容易想到另一种情况，即输入是3，1，3时，第一格中的接水量应该为3，而不是取两个挡板的最小值1。因为如果两侧有更高的挡板，那么此时会“淹掉”较矮的挡板，而接水量取决于左右两侧最高的挡板。所以这里需要修改一下上面的结论。修改成什么样呢？这里建议读者可以自己先想一下。

。。。。。。。。。。

。。自行思考地带。。

。。。。。。。。。。

好了，我们来说结论：接水量取决于左边的最大值和右边的最大值中的最小值

接水量结论

好了到这里基本的思路是清晰的，建议读者可以自己动动手实践一下。

我们知道，代码是“练”会的，不是“看”会的。

。。。。。。。。。。

。。自行实践地带。。

。。。。。。。。。。

完整版代码

接雨水

可以注意一下数组方法slice的使用，用以分割数组。

用法：

[1,2,3,4].slice(0,2)返回 [1,2]，即从0号下标元素开始（包含），到2号下标结束（不包含）的数组

[1,2,3,4].slice(1)返回 [2,3,4]，即从0号下标素开始（包含），到结尾的数组

总结

上述方法的复杂度分析如下：

时间复杂度O(n2)：一层循环内，每次取最大值也是O(n)的复杂度，因此相当于两层循环

空间复杂度O(n)：使用了一个新数组来存每一格的接水量

读者朋友，你能想到其他更高效或更有趣的解决方法么？

欢迎留言讨论