Class Solution

Stack/TrappingRainWater.py:85–118

"""
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        stack = [0]

        i = 1
        length = len(height)
        result = [0] * length
        
        while i < length:
            if height[i] <= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                mins = min(height[stack[0]], height[i])
                index = 0
                for j in xrange(stack[0], i):
                    _ = mins - height[j]

                    if _ > 0 and _ > result[j]:
                        result[j] = _
                
                if height[stack[0]] <= height[i]:
                    stack = []
                else:
                    stack = [stack[0]]
                
                stack.append(i)
                i += 1

        return sum(result)