接雨水问题详解
问题描述
给定一个非负整数数组 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 <= 10^5
解题思路
方法一：单调栈
单调栈是一种利用栈结构来解决此类问题的方法。其核心思想是通过维护一个单调递减的栈，来找到每个柱子左右两侧的“边界”，从而计算出能接的雨水量。
算法步骤
- 初始化一个栈 st，用于存储柱子的索引。
- 遍历数组 height，对于每个柱子：
- 如果当前柱子高度大于栈顶柱子的高度（即发现更高的右边界），则：
- 弹出栈顶元素（作为中间柱子）。
- 如果栈不为空，则计算当前柱子与栈顶柱子之间的雨水量：
- 高度差：h = min(height[st.top()], height) - 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;
- }
- };
- 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 = max(leftMax[i-1], height)
- rightMax = max(rightMax[i+1], height)
- 遍历数组 height，计算每个柱子能接的雨水量：
- result += min(leftMax, rightMax) - height
代码实现
- 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;
- }
- };
- 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)。最优解，适合对空间复杂度要求较高的场景。
接雨水这个经典标题，看似很难，但是现实上只是考察单调栈的利用。别的照旧很容易的。
视频学习保举
建议先参考以下视频进行学习：
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
