您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
收集雨水问题（Rain Water Trapping Problem）是计算机科学中一个经典的算法问题，通常在面试中作为考察候选人算法设计和优化能力的题目。该问题的核心在于如何高效地计算在一组不同高度的柱子之间能够收集多少雨水。本文将详细介绍如何使用C++解决这个问题，并探讨几种不同的解法及其优缺点。
给定一个非负整数数组 height，其中每个元素表示柱子的高度。假设这些柱子之间的宽度为1，计算在下雨之后，这些柱子之间能够收集多少雨水。
示例：
输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解释：在这种情况下，可以收集6个单位的雨水。
暴力解法的基本思路是对于数组中的每一个元素，找到其左边和右边的最大高度，然后取这两个最大高度的较小值，减去当前元素的高度，即为当前元素能够收集的雨水量。最后将所有元素的雨水量相加，即为总的雨水量。
int trap(vector<int>& height) {
int n = height.size();
int totalWater = 0;
for (int i = 0; i < n; ++i) {
int leftMax = 0, rightMax = 0;
for (int j = i; j >= 0; --j) {
leftMax = max(leftMax, height[j]);
}
for (int j = i; j < n; ++j) {
rightMax = max(rightMax, height[j]);
}
totalWater += min(leftMax, rightMax) - height[i];
}
return totalWater;
}
暴力解法的时间复杂度较高，主要是因为对于每个元素都需要遍历整个数组来找到其左边和右边的最大高度。我们可以通过预处理来优化这一过程。具体来说，我们可以使用两个数组 leftMax 和 rightMax 来分别存储每个元素左边和右边的最大高度。这样，我们只需要遍历数组两次，分别填充 leftMax 和 rightMax 数组，然后再遍历一次数组来计算总的雨水量。
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
vector<int> leftMax(n), rightMax(n);
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 totalWater = 0;
for (int i = 0; i < n; ++i) {
totalWater += min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
leftMax 和 rightMax 数组，以及计算总的雨水量。动态规划解法虽然优化了时间复杂度，但仍然需要额外的空间来存储 leftMax 和 rightMax 数组。我们可以进一步优化空间复杂度，使用双指针的方法来在常数空间内解决问题。
具体来说，我们使用两个指针 left 和 right 分别指向数组的起始和末尾。同时，我们使用两个变量 leftMax 和 rightMax 来分别记录 left 指针左边和 right 指针右边的最大高度。在每一步中，我们比较 leftMax 和 rightMax 的大小，如果 leftMax 小于 rightMax，则移动 left 指针，并更新 leftMax 和雨水量；否则，移动 right 指针，并更新 rightMax 和雨水量。
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
int left = 0, right = n - 1;
int leftMax = height[left], rightMax = height[right];
int totalWater = 0;
while (left < right) {
if (leftMax < rightMax) {
++left;
leftMax = max(leftMax, height[left]);
totalWater += leftMax - height[left];
} else {
--right;
rightMax = max(rightMax, height[right]);
totalWater += rightMax - height[right];
}
}
return totalWater;
}
栈解法是一种基于单调栈的解决方案。我们可以使用一个栈来存储数组的索引，并按照从栈底到栈顶的高度递减的顺序来维护这个栈。当我们遇到一个比栈顶元素高的柱子时，说明可以形成一个凹槽来收集雨水，此时我们弹出栈顶元素，并计算雨水量。
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
stack<int> st;
int totalWater = 0;
for (int i = 0; i < n; ++i) {
while (!st.empty() && height[i] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty()) break;
int distance = i - st.top() - 1;
int boundedHeight = min(height[i], height[st.top()]) - height[top];
totalWater += distance * boundedHeight;
}
st.push(i);
}
return totalWater;
}
| 解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力解法 | O(n^2) | O(1) |
| 动态规划解法 | O(n) | O(n) |
| 双指针解法 | O(n) | O(1) |
| 栈解法 | O(n) | O(n) |
从表中可以看出，双指针解法在时间和空间复杂度上都表现最优，适合在实际应用中使用。
以下是四种解法的完整代码实现：
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
// 暴力解法
int trapBruteForce(vector<int>& height) {
int n = height.size();
int totalWater = 0;
for (int i = 0; i < n; ++i) {
int leftMax = 0, rightMax = 0;
for (int j = i; j >= 0; --j) {
leftMax = max(leftMax, height[j]);
}
for (int j = i; j < n; ++j) {
rightMax = max(rightMax, height[j]);
}
totalWater += min(leftMax, rightMax) - height[i];
}
return totalWater;
}
// 动态规划解法
int trapDP(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
vector<int> leftMax(n), rightMax(n);
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 totalWater = 0;
for (int i = 0; i < n; ++i) {
totalWater += min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
// 双指针解法
int trapTwoPointers(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
int left = 0, right = n - 1;
int leftMax = height[left], rightMax = height[right];
int totalWater = 0;
while (left < right) {
if (leftMax < rightMax) {
++left;
leftMax = max(leftMax, height[left]);
totalWater += leftMax - height[left];
} else {
--right;
rightMax = max(rightMax, height[right]);
totalWater += rightMax - height[right];
}
}
return totalWater;
}
// 栈解法
int trapStack(vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
stack<int> st;
int totalWater = 0;
for (int i = 0; i < n; ++i) {
while (!st.empty() && height[i] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty()) break;
int distance = i - st.top() - 1;
int boundedHeight = min(height[i], height[st.top()]) - height[top];
totalWater += distance * boundedHeight;
}
st.push(i);
}
return totalWater;
}
int main() {
vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
cout << "暴力解法: " << trapBruteForce(height) << endl;
cout << "动态规划解法: " << trapDP(height) << endl;
cout << "双指针解法: " << trapTwoPointers(height) << endl;
cout << "栈解法: " << trapStack(height) << endl;
return 0;
}
本文详细介绍了四种解决收集雨水问题的方法：暴力解法、动态规划解法、双指针解法和栈解法。每种方法都有其独特的思路和优缺点。在实际应用中，双指针解法因其较低的时间和空间复杂度而成为最优选择。然而，理解其他解法也有助于加深对问题的理解，并在不同的场景中选择最合适的解决方案。
通过本文的学习，读者应该能够掌握如何使用C++解决收集雨水问题，并能够在面试中灵活运用这些方法。希望本文对你有所帮助！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。