题目1-头条雨水算法问题(1)

题目1-头条雨水算法问题(1)

题目

有一组高度不同对台阶,由一组整数表示。数组中每个数是台阶的高度。
当开始下雨了,水足够多。台阶之间的水坑会积多少水呢?
编写一个函数,根据给出的数组计算积水量。
例如下图可以表示为数组[0,1,0,2,1,0,1,3,2,1,2,1],返回积水量6.
start

计算思路:

通过计算每一行的积水量来计算总的积水量。
对于最下面的一层来说,积水量等于从左边第一个不为0的地方开始,到右边第一个不为0的地方结束,中间的0的个数。
因此我们采用算一行,减去一行的形式进行计算。比如题目中的例子可以表示为。

当前第一行:
start2
横轴之上只有2个绿色的格子,计数2个,下移一行。

当前第一行:
first
横轴之上只有4个绿色的格子,计数4个,下移一行。

当前第一行:
second

横轴之上没有绿色的格子。

共计6个。

代码如下

除非注明,否则均为浮生笔记原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.dennisthink.com/2019/01/17/226/

2 thoughts on “题目1-头条雨水算法问题(1)

Leave a Reply

Your email address will not be published. Required fields are marked *