LeetCode-python 42.接雨水

题目链接
难度：困难       类型： 栈

---

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

示例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

---

图片来源于 https://leetcode-cn.com/problems/two-sum/solution/jie-yu-shui-by-leetcode/

• 找到数组中从下标 i 到最左端最高的条形块高度 。
• 找到数组中从下标 i 到最右端最高的条形块高度 。
• 扫描数组 并更新答案：
  累加 到 总面积上

代码实现

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_left = [0]         
        for h in height:             
            max_left.append(max(max_left[-1], h))
        max_right = 0    
        res = 0
        n = len(height)
        for i in range(n):
            max_right = max(max_right, height[n-i-1])
            
            res += min(max_right, max_left[n-i]) - height[n-i-1]
        return res

本文链接：https://www.jianshu.com/p/b29b12c4f7b1