墙之间的水坑能够装多少水?

在下图中,我们有不同高度的墙。这个图片由一个整数数组所代表,数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6],假如开始下雨了,那么墙之间的水坑能够装多少水呢?

1

以1×1的方块为单位计算容积。所以,在上边的图中下标为1以左的都会漏掉。下标7以右的也会漏掉。剩下的只有在1和6之间的一坑水,容积是10。

2

若知道区间的右边界比左边界高,则存水高度就是由左边界确定的,此时将左边界向右移动,途中就可以直接计算在该墙之上的存水量是多少。若在移动过程中遇到了比左边界高的墙,说明之前移动扫过的是一个单独的水坑。这种方法只需要遍历一次数组,时间复杂度O(n),还是比较巧妙的。

代码如下:

发表评论

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