题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
输出：6
解释：下面是由数组表示的高度图，在这种情况下，可以接6个单位的雨水（蓝色部分表示雨水）。示例 2：
输入：height = [4, 2, 0, 3, 2, 5]
输出：9暴力法
暴力法求解本题的基本思想是：遍历每个柱子，对于每个柱子，分别向其左右两侧寻找最高的柱子；然后，用这个最高柱子的高度减去当前柱子的高度，得到可能蓄水的高度。使用暴力法求解本题的主要步骤如下。
1、初始化结果变量total_rain为0，用于累加计算接住的雨水量。
2、遍历每个柱子的位置i，进行如下操作。
（1）找到位置i左侧的最大高度max_left，初始为0。
（2）找到位置i右侧的最大高度max_right，初始为0。
（3）向左遍历，更新max_left为左侧遇到的最大高度。
（4）向右遍历，更新max_right为右侧遇到的最大高度。
（5）计算当前位置能接住的雨水量：min(max_left, max_right) - height[i]，并累加到total_rain中。
3、返回最终的total_rain作为结果。
根据上面的算法步骤，我们可以得出下面的示例代码。
def trap_rainwater_by_brute_force(height):
n = len(height)
total_rain = 0
for i in range(n):
max_left, max_right = 0, 0
# 寻找左侧最大高度
for j in range(i, -1, -1):
max_left = max(max_left, height[j])
# 寻找右侧最大高度
for j in range(i, n):
max_right = max(max_right, height[j])
# 当前柱子能接住的雨水量
rain = min(max_left, max_right) - height[i]
# 累加雨水量
total_rain += rain if rain > 0 else 0
return total_rain
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap_rainwater_by_brute_force(height))
height = [4, 2, 0, 3, 2, 5]
print(trap_rainwater_by_brute_force(height))动态规划法
动态规划法求解本题的基本思想是：从左到右、从右到左各遍历一次数组，分别计算出到当前位置为止的最高柱子高度，并利用这两个信息来确定当前位置能存多少雨水。使用动态规划法求解本题的主要步骤如下。
1、初始化两个数组 leftMax 和 rightMax，长度与原数组相同。leftMax[i] 存储索引 i 左侧（包括 i）的柱子中的最大高度，而 rightMax[i] 存储索引 i 右侧（包括 i）的柱子中的最大高度。
2、先从左向右遍历一次 height 数组，更新 leftMax 数组。对于每个位置 i，如果 height[i] 大于当前的 leftMax[i-1]，则 leftMax[i] = height[i]；否则 leftMax[i] = leftMax[i-1]。
3、再从右向左遍历一次 height 数组，更新 rightMax 数组。对于每个位置 i，如果 height[i] 大于当前的 rightMax[i+1]，则 rightMax[i] = height[i]；否则 rightMax[i] = rightMax[i+1]。
4、遍历 height 数组，对于每个位置 i，计算能接的雨水量为 min(leftMax[i], rightMax[i]) - height[i]，并累加这些值作为最终结果。
根据上面的算法步骤，我们可以得出下面的示例代码。
def trap_rainwater_by_dp(height):
n = len(height)
leftMax = [0] * n
rightMax = [0] * n
waterTrap = 0
# 从左到右计算 leftMax
leftMax[0] = height[0]
for i in range(1, n):
leftMax[i] = max(leftMax[i-1], height[i])
# 从右到左计算 rightMax
rightMax[n-1] = height[n-1]
for i in range(n-2, -1, -1):
rightMax[i] = max(rightMax[i+1], height[i])
# 计算雨水量
for i in range(n):
waterTrap += min(leftMax[i], rightMax[i]) - height[i]
return waterTrap
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap_rainwater_by_dp(height))
height = [4, 2, 0, 3, 2, 5]
print(trap_rainwater_by_dp(height))双指针法
双指针法求解本题的基本思想是：使用两个指针从数组的两端开始向中间移动，同时维护两个变量来记录左右两边的最大高度。这样可以在遍历过程中直接计算每个位置能接住的雨水量，而无需提前计算完整的左右最大高度数组。使用双指针法求解本题的主要步骤如下。
1、初始化两个指针 left 和 right 分别指向数组的开始和结束。
2、初始化两个变量 max_left 和 max_right 分别保存 left 和 right 指针所在位置左侧和右侧的最大高度，初始值都设为0。
3、用一个变量 water 来累计能接住的雨水量。
4、当 left < right 时，进行以下步骤。
（1）如果 height[left] < height[right]，说明当前能接雨水的量受限于 height[left]。因此，更新 max_left 为 max(max_left, height[left])，并且累加到 water 中的雨水量为 max_left - height[left]。然后，将 left 指针向右移动一位。
（2）反之，如果 height[left] >= height[right]，说明当前能接雨水的量受限于 height[right]。因此，更新 max_right 为 max(max_right, height[right])，累加到 water 中的雨水量为 max_right - height[right]，并将 right 指针向左移动一位。
5、当 left >= right 时，遍历结束，返回累积的雨水量 water。
根据上面的算法步骤，我们可以得出下面的示例代码。
def trap_rainwater_by_two_pointers(height):
left, right = 0, len(height) - 1
max_left, max_right = 0, 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap_rainwater_by_two_pointers(height))
height = [4, 2, 0, 3, 2, 5]
print(trap_rainwater_by_two_pointers(height))总结
暴力法通过遍历每个柱子，分别计算其左右两边的最大高度，从而确定当前位置能储存的雨水量。这种方法简单直接，但效率低下，时间复杂度为O(n^2)，不适用于大规模数据。
动态规划法利用两个数组分别记录从左到右和从右到左扫描过程中的最大高度，然后遍历每个柱子，计算雨水量。这种方法相比暴力法显著提高了效率，时间复杂度为O(n)，空间复杂度也为O(n)。
双指针法实际上是一种优化后的动态规划法，不需要额外存储空间。使用两个指针从数组两端开始向中间移动，同时维护两个变量记录左右两边的最大高度。该方法同样具有O(n)的时间复杂度，但空间复杂度降为O(1)。