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


CouPon

alibaba cloud20 dollars
Vultr10 Dollars
Bandwagon HostMaybe some Coupon?
Domain | namesiloemperinter 1Dollars