给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5] 输出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
解法一:
/** * @param {number[]} height * @return {number} */ var trap = function (height) { let left = 0; let right = height.length - 1; let sum = 0; let leftMax = 0; let rightMax = 0; while (left < right) { if (height[left] <= height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { sum += leftMax - height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { sum += rightMax - height[right]; } right--; } } return sum; };
说明:
要计算给定柱子高度图中的接雨水量,我们可以使用双指针的方法进行计算。这个问题通常被称为“接雨水问题”(Trapping Rain Water Problem)。
方法:双指针
算法步骤
初始化指针和变量:
左指针
left
指向数组的开始位置(索引 0)。右指针
right
指向数组的结束位置(索引n-1
)。初始化
left_max
和right_max
分别为柱子高度的初始左端和右端。初始化
water_trapped
变量为 0,用于存储总的接雨水量。遍历柱子高度数组:
如果
height[left]
小于等于height[right]
:否则:
如果
height[left]
大于等于left_max
,则更新left_max
。否则,计算当前位置能接的水量为
left_max - height[left]
,并将该水量累加到water_trapped
。移动左指针,即
left
增加 1。如果
height[right]
大于等于right_max
,则更新right_max
。否则,计算当前位置能接的水量为
right_max - height[right]
,并将该水量累加到water_trapped
。移动右指针,即
right
减少 1。当
left
小于right
时,进行以下操作:返回结果:
当循环结束时,
water_trapped
即为接雨水的总量。
算法实现
下面是用 Python 实现的代码:
def trap(height): if not height: return 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] water_trapped = 0 while left < right: if height[left] <= height[right]: if height[left] >= left_max: left_max = height[left] else: water_trapped += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water_trapped += right_max - height[right] right -= 1 return water_trapped # 示例 height = [0,1,0,2,1,0,1,3,2,1,2,1] result = trap(height) print("能接的雨水总量:", result)
示例
输入:
height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:
6
解释
在这个例子中,按照这种高度排列的柱子,经过雨水积累后,能够接住的雨水总量为 6
。
复杂度分析
时间复杂度:O(n),其中 n 是柱子高度数组的长度。我们只需遍历一次数组。
空间复杂度:O(1),除了存储变量外,不需要额外的空间。
这种方法有效地利用了双指针技巧,通过一次遍历即可完成对接雨水量的计算,是解决该问题的常用方法之一。