Simple python solution


  • 0
    C

    This array was divided into 2 parts, and the boundary is the maximum number.(if the maximum number show twice or more times, just pick the first one)
    we use the same algorithm to review the array twice, from left to right and from right to left.
    before we meet the maximum number, as long as the height goes down, fill it with water, because we must encounter the other bar which is higher than any other. After we meet the maximum number, the fill algorithm fails.
    But start again from right to left, it can calculate the water from the other side. and add them together, the answer is correct

    class Solution(object):
        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            maxh=0
            water=0
            total=0
            for i in range(0,len(height)):
                if height[i]<maxh:
                    water+=(maxh-height[i])
                if height[i]>maxh:
                    maxh=height[i]
                    total+=water
                    water=0
            maxh=0        
            water=0
            for i in range(len(height)-1,-1,-1):
                if height[i]<maxh:
                    water+=(maxh-height[i])
                if height[i]>=maxh:
                    maxh=height[i]
                    total+=water
                    water=0
            return total
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.