堆栈解

leetcode 42 接雨水
堆栈解往往是 一个一个压入 连续地弹出
如果当前元素小于等于栈顶的元素 将其压入堆栈 因为当前元素可以被栈内的前一个元素兜住
如果当前元素大于了栈顶的元素 那么栈顶的元素可以被左边和右边的元素兜住 我们就可以计算兜住的雨水
连续弹出的时候 看以看出 雨水是被一层一层计算出来的

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

        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]: # 当前元素比栈内最后一个元素大
                mid = stack.pop()
                if not stack:
                    break
                distance = i - stack[-1] - 1
                bounded_height = min(height[i], height[stack[-1]]) - height[mid]
                res += distance * bounded_height
            stack.append(i)
        return res

image.png

各种括号问题 先占坑吧...