---

题目

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

示例1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

---

答案

动态规划

我们定义 left[i] 表示下标 i 位置及其左边的最高柱子的高度，定义 right[i] 表示下标 i 位置及其右边的最高柱子的高度。那么下标 i 位置能接的雨水量为 min(left[i],right[i])−height[i]。我们遍历数组，计算出 left[i] 和 right[i]，最后答案为 ${\sum }_{i=0}^{n-1}min(left[i],right[i])-height[i]$ 。

时间复杂度 O(n)，空间复杂度 O(n)。其中 n 为数组的长度。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        left = [height[0]] * n
        right = [height[-1]] * n
        for i in range(1, n):
            left[i] = max(left[i - 1], height[i])
            right[n - i - 1] = max(right[n - i], height[n - i - 1])
        return sum(min(l, r) - h for l, r, h in zip(left, right, height))

---

运行结果