【面试题】接雨水
接雨水
仅学习
一、问题描述
二、解调思路
这个问题是一个典型的双指针问题，也称为"接雨水问题"。我们可以通过遍历数组两次来解决这个问题：一次从左到右，一次从右到左，分别记录每个位置左边和右边的最大高度。然后，可以计算每个柱子能够接住的雨水量，即两边较小的最大高度减去当前柱子的高度，如果这个值大于0，则表示可以接住雨水。
三、代码
def trap(height):if not height:return 0n = len(height)left_max = [0] * nright_max = [0] * nwater_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列表，计算每个位置能够接住的雨水量，并将它们累加起来得到最终的结果。