42-TrappingRainWater

Trapping Rain Water

Problem can be found in here!

Solution: Monotonic Stack

def trap(heights: List[int]) -> int:
    area = 0
    stack = []
    for i in range(len(heights)):
        while stack and heights[stack[-1]] < heights[i]:
            candidate = heights[stack.pop()]
            if stack:
                height = min(heights[i], heights[stack[-1]]) - candidate
                width = i - stack[-1] - 1
                area += height * width
        stack.append(i)

    return area

Explanation: Please refer to link for explanation.

Time Complexity: , Space Complexity: