Python solution


  • 0

    My idea is like this:
    We check the left most bar and right most bar, if the left most bar is smaller or equal to the right most bar, we know that the water level on the right side of the left most bar should be at the left most bar's level. Can you imagine that? So, how far to the right can we go from here? Of course, only to the point we find a higher bar than the left most bar. At this point we have to check the height of our new left most bar with out right most bar. Keep doing this until those 2 pointers meet each other.

    class Solution(object):
        def trap(self, height):
            s = 0
            l, r = 0, len(height)-1
            while l < r:
                i = 1
                if height[l] < height[r]:
                    while height[l] > height[l+i]:
                        s += height[l] - height[l+i]
                        i += 1
                    l += i
                else:
                    while height[r] > height[r-i]:
                        s += height[r] - height[r-i]
                        i += 1
                    r -= i
            return s
    

Log in to reply
 

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