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.

• https://leetcode.com/problems/trapping-rain-water/

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

https://blog.emperinter.info/2022/04/23/trapping-rain-water