接雨水
仅学习
一、问题描述
二、解调思路
这个问题是一个典型的双指针问题，也称为"接雨水问题"。我们可以通过遍历数组两次来解决这个问题：一次从左到右，一次从右到左，分别记录每个位置左边和右边的最大高度。然后，可以计算每个柱子能够接住的雨水量，即两边较小的最大高度减去当前柱子的高度，如果这个值大于0，则表示可以接住雨水。
三、代码
def trap(height): if not height: return 0 n = len(height) left_max = [0] * n right_max = [0] * n water_trapped = 0 # 从左到右找到每个位置左边的最大高度 left_max[0] = height[0] for i in range(1, n): left_max[i] = max(left_max[i - 1], height[i]) # 从右到左找到每个位置右边的最大高度 right_max[n - 1] = height[n - 1] for i in range(n - 2, -1, -1): right_max[i] = max(right_max[i + 1], height[i]) # 计算雨水量 for i in range(n): water_trapped += min(left_max[i], right_max[i]) - height[i] return water_trapped # 示例 print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 输出：6 print(trap([4,2,0,3,2,5])) # 输出：9
这段代码首先定义了一个函数trap，它接受一个表示柱子高度的列表。然后，使用两个数组left_max和right_max来分别存储每个位置左边和右边的最大高度。接着，遍历这个列表两次，一次从左到右，一次从右到左，填充这两个数组。最后，遍历原始的height列表，计算每个位置能够接住的雨水量，并将它们累加起来得到最终的结果。
