【Leetcode刷题Python】42. 接雨水

1 题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

2 解析

（1）方法一：栈 将墙的高度入栈，当新元素小于栈顶元素，就入栈，反之就出栈，并计算凹槽内的长和宽。最后将每个长方形面积求和。

注意：凹槽的高度是由 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度 来计算的。如下图的是左边的2号柱子的高度建议1号柱子的高度。 凹槽的宽度是由凹槽右边的下标 – 凹槽左边的下标 – 1（因为只求中间宽度）来计算的。

3 Python实现

class Solution:
    def trap(sel, height: List[int]) -> int:
        stack = []
        result = 0
        for i in range(len(height)):
            if not stack:
                stack.append(i)
            elif height[i]