题目要求

给定 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 * 104
0 <= height[i] <= 105

思考

我们这里的做法是通过两次填补实现对所有水坑的装水后的总占量减去不填水的占量得到水的占量
我们第一次从左到右遍历，对于当前位置i，我们从左向右寻找到第一个不小于他高度的柱子j，将中间全部填满，填满高度为当前位置i的高度和寻找到的高度中的小值。并且改变当前位置为已找到的位置j，并从j开始继续向后寻找。但是如此只能填满左低右高的水坑，我们还需要从左到右进行一次遍历，填满左高右低的水坑。 最终两块面积差就是我们最后填补的水坑。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        sum_sub1 = sum(height)
        l = len(height)
        i = 0
        while i < l-1:
            t = -1
            for j in range(i+1,l,1):
                if height[j] >= height[i]:
                    now_min = min(height[i],height[j])
                    for k in range(i+1,j):
                        height[k] = now_min
                    t = j
                if t != -1:
                    i = t
                    break
            if t == -1:
                i += 1

        i = l-1
        while i > -1:
            t = -1
            for j in range(i-1,-1,-1):
                if height[j] >= height[i]:
                    now_min = min(height[i],height[j])
                    for k in range(i-1,j,-1):
                        height[k] = now_min
                    t = j
                if t != -1:
                    i = t
                    break
            if t == -1:
                i -= 1

        sum_sub2 = sum(height)

        final = sum_sub2 - sum_sub1

        return final