接雨水问题详解
问题描述
给定一个非负整数数组 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.length1 <= n <= 2 * 10^40 <= 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)。最优解，适合对空间复杂度要求较高的场景。
接雨水这个经典题目，看似很难，但是实际上只是考察单调栈的使用。别的还是很容易的。
视频学习推荐
建议先参考以下视频进行学习：