每日一题——接雨水

接雨水问题详解

问题描述

给定一个非负整数数组 height，表示每个宽度为 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 * 10^4
0 <= height[i] <= 10^5

解题思路

方法一：单调栈

单调栈是一种利用栈结构来解决此类问题的方法。其核心思想是通过维护一个单调递减的栈，来找到每个柱子左右两侧的“边界”，从而计算出能接的雨水量。

算法步骤

初始化一个栈 st，用于存储柱子的索引。
遍历数组 height，对于每个柱子：
- 如果当前柱子高度大于栈顶柱子的高度（即发现更高的右边界），则：
  - 弹出栈顶元素（作为中间柱子）。
  - 如果栈不为空，则计算当前柱子与栈顶柱子之间的雨水量：
    - 高度差：h = min(height[st.top()], height[i]) - height[mid]
    - 宽度：w = i - st.top() - 1
    - 雨水量：sum += h * w
将当前柱子索引入栈。
遍历结束后，返回总雨水量。

C++代码实现

class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0; // 可以不加stack<int> st;int sum = 0;for (int i = 0; i < height.size(); i++) {while (!st.empty() && height[i] >= height[st.top()]) { // 发现有更高的右边界int mid = st.top(); // 单调栈第一个拿来当作盛水的低st.pop(); // 拿来用就给扔了，没用了if (!st.empty()) { // 看下单调栈是否为空，别是空的，保证左边能盛水int h = min(height[st.top()], height[i]) - height[mid]; // 这是找左边最大值int w = i - st.top() - 1; // 注意减一，只求中间宽度sum += h * w;}} // 注意while还在循环，因为右边多了一组墙，左边多了几组雨水st.push(i); // 把当前这个最大值扔进去，当作左边的墙}return sum;}
};

C语言代码实现

int trap(int* height, int heightSize) {int n = heightSize;if (n == 0) {return 0;}int ans = 0;int stk[n], top = 0;for (int i = 0; i < n; ++i) {while (top && height[i] > height[stk[top - 1]]) {int stk_top = stk[--top];if (!top) {break;}int left = stk[top - 1];int currWidth = i - left - 1;int currHeight = fmin(height[left], height[i]) - height[stk_top];ans += currWidth * currHeight;}stk[top++] = i;}return ans;
}

方法二：动态规划

动态规划的核心思想是通过维护两个数组 leftMax 和 rightMax，分别表示每个柱子左侧和右侧的最大高度。通过这两个数组，可以快速计算出每个柱子能接的雨水量。

算法步骤

初始化两个数组 leftMax 和 rightMax，分别表示每个柱子左侧和右侧的最大高度。
遍历数组 height，计算 leftMax 和 rightMax：
- leftMax[i] = max(leftMax[i-1], height[i])
- rightMax[i] = max(rightMax[i+1], height[i])
遍历数组 height，计算每个柱子能接的雨水量：
- result += min(leftMax[i], rightMax[i]) - height[i]

代码实现

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) return 0;vector<int> leftMax(n, 0);vector<int> rightMax(n, 0);leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = max(leftMax[i - 1], height[i]);}rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = max(rightMax[i + 1], height[i]);}int result = 0;for (int i = 0; i < n; i++) {result += min(leftMax[i], rightMax[i]) - height[i];}return result;}
};

方法三：双指针优化

动态规划的方法需要额外的 O(n) 空间来存储 leftMax 和 rightMax。通过使用双指针，可以将空间复杂度优化到 O(1)。

算法步骤

初始化两个指针 left 和 right，分别指向数组的两端。
初始化两个变量 leftMax 和 rightMax，分别表示左侧和右侧的最大高度。
当 left < right 时：
- 更新 leftMax 和 rightMax：
  - leftMax = max(leftMax, height[left])
  - rightMax = max(rightMax, height[right])
- 如果 height[left] < height[right]，则：
  - result += leftMax - height[left]
  - left++
- 否则：
  - result += rightMax - height[right]
  - right--
返回总雨水量。

代码实现

class Solution {
public:int trap(vector<int>& height) {int result = 0;int l = 0, r = height.size() - 1;int lMax = 0, rMax = 0;while (l < r) {lMax = max(lMax, height[l]);rMax = max(rMax, height[r]);if (height[l] < height[r]) {result += lMax - height[l];++l;} else {result += rMax - height[r];--r;}}return result;}
};

C语言代码实现

int trap(int* height, int heightSize) {int result = 0;                // 用于存储最终能接的雨水总量int l = 0, r = heightSize - 1; // 初始化左右指针，l指向数组起始位置，r指向数组末尾位置int lMax = 0, rMax = 0;        // 初始化左右最大高度变量，用于记录左右指针遍历过程中的最大柱子高度// 当左指针小于右指针时，继续循环，直到两个指针相遇while (l < r) {// 更新左指针左侧的最大高度lMax = lMax > height[l] ? lMax : height[l]; // 如果当前左指针指向的柱子高度大于lMax，则更新lMax// 更新右指针右侧的最大高度rMax = rMax > height[r] ? rMax : height[r]; // 如果当前右指针指向的柱子高度大于rMax，则更新rMax// 根据左右指针指向的柱子高度，决定移动哪个指针if (height[l] < height[r]) {// 如果左指针指向的柱子高度小于右指针指向的柱子高度// 说明左指针处的柱子可以确定其能接的雨水量（由左最大值lMax决定）result += lMax - height[l]; // 计算当前左指针处能接的雨水量，并累加到result中++l;                        // 左指针向右移动一位} else {// 如果左指针指向的柱子高度大于等于右指针指向的柱子高度// 说明右指针处的柱子可以确定其能接的雨水量（由右最大值rMax决定）result += rMax - height[r]; // 计算当前右指针处能接的雨水量，并累加到result中--r;                        // 右指针向左移动一位}}// 当左右指针相遇时，遍历结束，返回能接的雨水总量return result;
}

总结

单调栈：时间复杂度 O(n)，空间复杂度 O(n)。适合对空间复杂度要求不高的场景。
动态规划：时间复杂度 O(n)，空间复杂度 O(n)。思路清晰，适合初学者理解。
双指针优化：时间复杂度 O(n)，空间复杂度 O(1)。最优解，适合对空间复杂度要求较高的场景。
接雨水这个经典题目，看似很难，但是实际上只是考察单调栈的使用。别的还是很容易的。