9 lines clean Python solution using stack with one pass


  • 0
    V
    class Solution(object):
        def trap(self, height):
            s, water = [], 0
            for j, h in enumerate(height):
                while s and height[s[-1]] <= h:
                    i2 = s.pop()
                    if not s: break
                    diff = min(height[s[0]], h) - height[i2]
                    water += diff * (i2 - s[-1])
                s.append(j)
            return water
    

Log in to reply
 

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