收集雨水問題（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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
