42. Trapping Rain Water
Given n
non-negative integers representing an elevation map where the width of each bar is 1
, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
# @lc code=start
using LeetCode
function trap_rain(height::Vector{Int})::Int
csum = cumsum(height)
pushfirst!(csum, 0)
max_pos = argmax(height)
len = length(height)
res = 0
r = 1
for i in 2:max_pos
if height[i] >= height[r]
res += (i > r + 1) * (height[r] * (i - r) - (csum[i] - csum[r]))
r = i
end
end
l = len
for j in (len - 1):-1:max_pos
if height[j] >= height[l]
res += (j < l - 1) * (height[l] * (l - j) - (csum[l + 1] - csum[j + 1]))
l = j
end
end
return res
end
# @lc code=end
trap_rain (generic function with 1 method)
This page was generated using DemoCards.jl and Literate.jl.