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

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

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

题目

输入:[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):使用了一个新数组来存每一格的接水量

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

欢迎留言讨论

1.《程序员面试题之“接雨水”》援引自互联网,旨在传递更多网络信息知识,仅代表作者本人观点,与本网站无关,侵删请联系页脚下方联系方式。

2.《程序员面试题之“接雨水”》仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证。

3.文章转载时请保留本站内容来源地址,https://www.cxvn.com/gl/djyxgl/161270.html