给定 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
方法一：暴力（Python 超时）
从最原始的暴力解法开始思考，对于每个下标 i，我们计算它上方可以接多少雨水，然后将所有下标上的雨水加起来即可。
具体来说，如图我们假设输入为 [0,1,0,2]，凭感觉，我们得到接完雨水后的结果如右图。可以看到，只有下标 2 的上方可以接到雨水，其他地方的水会向两边“流掉”，所以无法接到水。
为什么是这样呢？首先看下标 1 ，它左边最高的柱子是下标 0 ，右边最高的柱子是下标 3 ，因为这两个柱子的较小值比下标 1 要低，所以下标 1 的上方没有水。相反，我们看下标 2，它左边最高的柱子是下标 1 ，右边最高的柱子是下标 3 ，这两个柱子较矮的是下标 1 ，它比下标 2 本身要高，所以下标 2 可以接到水，接的水就是高度差。
因此，我们遍历每个下标，寻找它左边和右边最高的柱子，判断是否可以接到水，将可接水的结果累加即可。
示例代码：
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
n = len(height)
for i in range(n):
max_left, max_right = 0, 0
# 寻找 max_left
for j in range(0,i):
max_left = max(max_left, height[j])
# 寻找 max_right
for j in range(i, n):
max_right = max(max_right, height[j])
minn = min(max_left, max_right)
if minn > height[i]:
ans += minn - height[i]
return ans
复杂度分析
- 时间复杂度：O(N^2)。最坏情况下，我们对于每个下标，都要向左和向右遍历直到两端，复杂度是 N 的平方。
- 空间复杂度：O(1)。使用了有限的 n, ans, maxleft, maxright。
方法二：动态规划
在寻找每个下标的左边和右边最高的柱子时，会对柱子进行反复搜索导致复杂度降低，假如我们使用两个数组 maxleft 和 maxright，maxleft[i] 表示下标 i 左边最高柱子的高度,maxright[i] 表示下标 i 右边最高柱子的高度，很明显，我们只需要一趟遍历就可以得到结果。这样由于避免了重复计算，时间复杂度会降低到 O(N)。
示例代码：
class Solution:
def trap(self, height: List[int]) -> int:
# 边界条件
if not height:
return 0
n = len(height)
ans = 0
max_left = [0] * n
max_right = [0] * n
# 初始化
max_left[0] = height[0]
max_right[n-1] = height[n-1]
# 设置备忘录，分别存储左边和右边最高的柱子高度
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
for i in range(n-2,-1,-1):
max_right[i] = max(max_right[i+1], height[i])
# 一趟遍历，比较每个位置可以存储多少水
for i in range(n):
minn = min(max_left[i], max_right[i])
if minn > height[i]:
ans += minn - height[i]
return ans
方法三：双指针法
双指针法就是将上边的一个下标 i，变为两个下标 left，right，分别位于输入数组的两端。向中间移动时，边移动边计算。
除此之外，我们使用 maxleft 作为 0...left 的最大值，maxright 作为 right...结尾 的最大值。
示例代码：
class Solution:
def trap(self, height: List[int]) -> int:
# 边界条件
if not height:
return 0
n = len(height)
ans = 0
max_left, max_right = height[0], height[n-1]
left, right = 0, n-1
while left <= right:
max_left = max(max_left, height[left])
max_right = max(max_right, height[right])
if max_left < max_right:
ans += max_left - height[left]
left += 1
else:
ans += max_right - height[right]
right -= 1
return ans
复杂度分析
- 时间复杂度：O(N)。遍历了一遍数组。
- 空间复杂度：O(1)。使用了有限的 left, right, ans, maxleft, maxright。
