题目：

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

1

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

题目的理解：

从示例图中可以很好的理解，题目的意思，真的是题目描述越少越难。
最直接的思路：
（1）为一个高度创建一个数组A，值是所在的索引。组成一个大数组C。
（2）取出height中的最大值，进行遍历。
（3）C中存在的值就记录到数组D中。那么计算D中空缺的位数，就是可以存放雨水的数量。
（4）求雨水的总和就是结果。

from typing import  List


class Solution:
    def trap(self, height: List[int]) -> int:
        if 2 > len(height):
            return 0
        
        columns = list()

        for index, num in enumerate(height):
            columns.append([index] * num)

        trap = 0
        height_max = max(height)
        for index in range(height_max):
            rows = list()

            for column in columns:
                if index < len(column):
                    rows.append(column[index])

            trap += (max(rows) - min(rows) + 1) - len(rows)

        return trap

从时间复杂度上算有O(N + N*N), 计算超时了，需要减少时间复杂度。
可以减少上面的步骤1，就是不进行创建数组C，即减少了时间复杂度又减少了空间复杂度。

from typing import  List


class Solution:
    def trap(self, height: List[int]) -> int:
        if 2 > len(height):
            return 0

        trap = 0
        for floor in range(max(height)):
            rows = list()

            for index, column in enumerate(height):
                if floor < column:
                    rows.append(index)

            trap += (max(rows) - min(rows) + 1) - len(rows)

        return trap

这时的时间复杂度为O(N * N), 计算还是超时了。再think think think。。。

总结起来，也就是当使用多个循环的时候，那么大概率会出现计算超时，如果使用动态规则也就是递归来处理的时候，大概率是能成功的。
使用动态规则的思路：
（1）找到最大值的索引S，向左找最大值索引A，计算雨水。从A继续向左遍历。
（2）从S向右找最大值索引B，计算雨水。从B继续向右遍历。
（3）返回雨水总和。

python实现

from typing import  List


class Solution:
    def trap(self, height: List[int]) -> int:
        if 2 > len(height):
            return 0

        self.total_drop = 0

        def calc_trap(standard, start, end) -> int:
            drop = 0
            for value in height[start: end]:
                drop += standard - value

            return drop

        def left_recursion(index):
            temp_height = height[: index]
            max_height = max(temp_height)
            max_index = temp_height.index(max_height)

            self.total_drop += calc_trap(min(height[index], height[max_index]), max_index, index)

            if max_index > 0:
                left_recursion(max_index)

        def right_recursion(index):
            temp_height = height[index + 1:]
            max_height = max(temp_height)
            max_index = temp_height.index(max_height) + index + 1

            self.total_drop += calc_trap(min(height[index], height[max_index]), index + 1, max_index)

            if max_index != len(height) - 1:
                right_recursion(max_index)

        max_height = max(height)
        max_index = height.index(max_height)
        if max_index > 0:
            left_recursion(max_index)
        if max_index != len(height) - 1:
            right_recursion(max_index)

        return self.total_drop

想看最优解法移步此处

提交

success

// END 有时候就是要静下心来，多思考，发现路子很多很宽