谷歌（Google）历年编程真题——接雨水

谷歌历年面试真题——数组和字符串系列真题练习。

接雨水

给定 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

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

思路一：双指针

这个问题可以使用双指针的方法来解决。具体步骤如下：

1. 初始化左右指针 left 和 right，分别指向数组的第一个和最后一个元素。
2. 初始化两个变量 left_max 和 right_max，分别表示左侧柱子的最大高度和右侧柱子的最大高度，初始值都为0。
3. 使用循环遍历数组，当 left 指针小于等于 right 指针时，执行以下步骤：
   • 如果 height[left] < height[right]，表示左侧柱子较低，则计算当前位置的雨水量，并更新左侧最大高度 left_max。
   • 否则，表示右侧柱子较低，则计算当前位置的雨水量，并更新右侧最大高度 right_max。
   • 在计算雨水量时，当前位置能够接的雨水量等于当前最小高度（left_max和right_max中的较小值）与当前柱子高度之差。
4. 返回计算得到的总雨水量。

下面是相应的Python代码实现：

def trap(height):if not height:return 0left, right = 0, len(height) - 1left_max, right_max = 0, 0ans = 0while left <= right:if height[left] < height[right]:if height[left] >= left_max:left_max = height[left]else:ans += left_max - height[left]left += 1else:if height[right] >= right_max:right_max = height[right]else:ans += right_max - height[right]right -= 1return ans# 示例 1
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1))  # 输出：6# 示例 2
height2 = [4,2,0,3,2,5]
print(trap(height2))  # 输出：9

这个函数使用双指针的方法，通过一次遍历就可以计算出雨水的总量。

思路二：栈

除了双指针的方法外，还可以使用栈来解决这个问题。具体步骤如下：

1. 初始化一个栈 stack 和一个变量 ans，ans 用于记录接到的雨水量，初始值为0。
2. 遍历数组 height 中的每一个柱子，依次执行以下操作：
   • 如果栈为空，或当前柱子高度小于等于栈顶柱子高度，则将当前柱子下标入栈。
   • 否则，说明当前柱子可能会形成一个水池，将栈中元素逐个弹出，直到遇到柱子高度大于当前柱子高度的位置。每次弹出时，都计算当前柱子和栈顶柱子之间的距离，并根据距离和高度差计算雨水量，然后累加到 ans 中。
   • 最后将当前柱子下标入栈。
3. 遍历完成后，返回 ans 即为最终的雨水量。

下面是相应的 Python 代码实现：

def trap(height):stack = []ans = 0for i in range(len(height)):while stack and height[i] > height[stack[-1]]:top = stack.pop()if not stack:breakdistance = i - stack[-1] - 1bounded_height = min(height[i], height[stack[-1]]) - height[top]ans += distance * bounded_heightstack.append(i)return ans# 示例 1
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1))  # 输出：6# 示例 2
height2 = [4,2,0,3,2,5]
print(trap(height2))  # 输出：9

这个函数使用栈的方法，通过一次遍历就可以计算出雨水的总量。

思路三：动态规划

除了双指针和栈的方法外，还可以使用动态规划来解决这个问题。具体步骤如下：

1. 初始化两个数组 left_max 和 right_max，分别用于存储每个柱子左侧和右侧的最大高度。
   • left_max[i] 表示第 i 个柱子左侧（包括自身）的最大高度。
   • right_max[i] 表示第 i 个柱子右侧（包括自身）的最大高度。
2. 遍历数组 height，从左向右更新 left_max，从右向左更新 right_max。
3. 遍历数组 height，对于每个柱子，计算该位置上可以接到的雨水量，即 min(left_max[i], right_max[i]) - height[i]。
4. 累加所有位置上的雨水量，即为最终的雨水总量。

下面是相应的 Python 代码实现：

def trap(height):n = len(height)if n == 0:return 0left_max = [0] * nright_max = [0] * n# 初始化 left_maxleft_max[0] = height[0]for i in range(1, n):left_max[i] = max(left_max[i - 1], height[i])# 初始化 right_maxright_max[n - 1] = height[n - 1]for i in range(n - 2, -1, -1):right_max[i] = max(right_max[i + 1], height[i])# 计算雨水量ans = 0for i in range(n):ans += min(left_max[i], right_max[i]) - height[i]return ans# 示例 1
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height1))  # 输出：6# 示例 2
height2 = [4,2,0,3,2,5]
print(trap(height2))  # 输出：9

这个函数使用动态规划的方法，通过三次遍历就可以计算出雨水的总量。