题目：
给定 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 有时候就是要静下心来，多思考，发现路子很多很宽
