Simple Pyhton Solution, easy to understand


  • 1
    S
    class Solution(object):
        def trap(self, height):
            n= len(height)
            if n<=1: return 0 
            left= [0 for i in xrange(n)] #denotes max before this element including this
            right= [0 for i in xrange(n)] #denotes max after this element including this
            left[0], right[-1]= height[0], height[-1] 
            for i in xrange(1,n):
                left[i]= max(left[i-1], height[i])
            for i in xrange(n-2,-1,-1):
                right[i]= max(right[i+1], height[i])
            tatal_water= 0
            for i in xrange(n):
                caused_by_this= min(left[i], right[i])- height[i] #water collected by this bar 
                tatal_water+= caused_by_this
            return tatal_water

Log in to reply
 

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