Python using stack Easy to understand


  • 0

    Use stack to maintain a list of decreasing heights. Pop the heights that are lower than the current height, and do volume calculations. Use a bar to record the level to avoid repeated computation. Remember to compute the highest level of water if there’s some block in stack that is higher than the current height.

    class Solution(object):
        def trap(self, height):
            res = 0
            stack = []
            for i, h in enumerate(height):
                temp = bar = 0
                while stack and h >= stack[-1][1]:
                    p_i, p_h = stack.pop()
                    temp += (i - p_i - 1) * (p_h - bar)
                    bar = p_h
                if stack:
                    temp += (i - stack[-1][0] - 1) * (h - bar)
                res += temp
                stack.append((i, h))
            return res
    

Log in to reply
 

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