Trapping Rain Water
The Post Created(Updated) On 04/23/2022,Please note the timeliness of the article!
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.
Solution
Double Link
Code
- submit code
class Solution:
def trap(self, height: List[int]) -> int:
if len(height)<3:
return 0
ret = 0
l_max = [0]*len(height)
r_max = [0]*len(height)
# base case
l_max[0] = height[0]
r_max[-1] = height[-1]
# find l_max
for i in range(1,len(height)):
l_max[i] = max(l_max[i-1],height[i])
# find r_max
for j in range(len(height)-2,0,-1):
r_max[j] = max(r_max[j+1],height[j])
# find water
for k in range(1,len(height)-1):
ret += min(l_max[k],r_max[k]) - height[k]
return ret
- full code
class SolutionMinTime:
def trap(self,height):
if len(height)<3:
return 0
ret = 0
l_max = [0]*len(height)
r_max = [0]*len(height)
# base case
l_max[0] = height[0]
r_max[-1] = height[-1]
# find l_max
for i in range(1,len(height)):
l_max[i] = max(l_max[i-1],height[i])
# find r_max
for j in range(len(height)-2,0,-1):
r_max[j] = max(r_max[j+1],height[j])
# find water
for k in range(1,len(height)-1):
ret += min(l_max[k],r_max[k]) - height[k]
return ret
SMT = SolutionMinTime()
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(SMT.trap(height))
#6
Copyright
Unless otherwise noted, all work on this blog is licensed under a Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) License. Reprinted with permission from -https://blog.emperinter.info/2022/04/23/trapping-rain-water