题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
解答
不难发现,能够接水的条件是左右两边的柱子都高于自己,并且取决于左右两边矮的那个。
那么不必每个凹槽一起算,可以算每个格子对于答案的共享,然后累加答案。
可以正序,逆序各遍历一遍数组,得到每个格子左边、右边的最高的值,分别用一个数组存储。
然后遍历一遍累加得到答案。
Java实现:
1 | class Solution { |
时间复杂度 : O ( n )
空间复杂度: O ( n )
提交之后发现空间复杂度有点高了。
看了一下题解,原来可以把那个数组优化掉。(艹,又是双指针)
由于每个格子对答案的贡献只取决于左右两边低的那个,可以发现:
如果右边有更高的格子,那么当前位置积水的高度可以根据左边计算,并且可以算接下来(方向从左到右)的格子,因为当前格子已经不会再对后面的格子产生影响。反之亦然。
所以我们可以设置前后两个指针,同时维护左边最大值 lmax 和右边最大值 rmax ,当右边指针格子更高时,处理左边,根据当前格子高度与左边的最大值的关系来决定更新答案或者更新最大值。反之亦然。
Java实现:
1 | class Solution { |
时间复杂度 : O ( n )
空间复杂度: O ( 1 )