227
[LeetCode]42.Trapping Rain Water
【題目】
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
【題意】
給定n個非負整數，代表一個柱狀圖，每一個柱子的寬度為1，計算下雨之後柱狀圖能裝多少水？
例如：
[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個單位的雨水（藍色部分）被裝。
【分析】
對於每個柱子，找到其左右兩邊最高的柱子，該柱子能容納的麵積就是 min(leftMostHeight,rightMostHeight) - height。所以，
1. 從左往右掃描一遍，對於每個柱子，求取左邊最大值；
2. 從右往左掃描一遍，對於每個柱子，求最大右值；
3. 再掃描一遍，把每個柱子的麵積並累加。
也可以，
1. 掃描一遍，找到最高的柱子，這個柱子將數組分為兩半；
2. 處理左邊一半；
3. 處理右邊一半。
【代碼】
/*---------------------------------------
* 日期：2014-01-20
* 作者：SJF0115
* 題目: 42.Trapping Rain Water
* 網址：https://oj.leetcode.com/problems/trapping-rain-water/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------*/
class Solution {
public:
int trap(int A[], int n) {
if(A == NULL || n < 1)return 0;
int i;
int* leftMostHeight = (int*)malloc(sizeof(int)*n);
int* rightMostHeight = (int*)malloc(sizeof(int)*n);
int maxHeight = 0;
for(i = 0; i < n;i++){
leftMostHeight[i] = maxHeight;
if(maxHeight < A[i]){
maxHeight = A[i];
}
}
maxHeight = 0;
for(i = n-1;i >= 0;i--){
rightMostHeight[i] = maxHeight;
if(maxHeight < A[i]){
maxHeight = A[i];
}
}
int water = 0;
for(i =0; i < n; i++){
int curWater = min(leftMostHeight[i],rightMostHeight[i]) - A[i];
if(curWater > 0){
water += curWater;
}
}
return water;
}
};
</pre><h4><span >【代碼2】</span></h4><p></p><pre code_snippet_ snippet_file_name="blog_20150512_2_1444678" name="code" >/*---------------------------------------
* 日期：2015-05-12
* 作者：SJF0115
* 題目: 42.Trapping Rain Water
* 網址：https://oj.leetcode.com/problems/trapping-rain-water/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
int size = height.size();
int result = 0;
if(size <= 0){
return result;
}//if
int leftMax[size];
int rightMax[size];
leftMax[0] = 0;
rightMax[size-1] = 0;
// 對於第i個元素 左右最大值
for(int i = 1;i < size;++i){
leftMax[i] = max(leftMax[i-1],height[i-1]);
rightMax[size-1-i] = max(rightMax[size-i],height[size-i]);
}//for
// 最大積雨量
int h;
for(int i = 0;i < size;++i){
h = min(leftMax[i],rightMax[i]);
if(h > height[i]){
result += h - height[i];
}//if
}//for
return result;
}
};
int main() {
Solution solution;
vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
cout<<solution.trap(height)<<endl;
return 0;
}
【代碼3】
思路2
/*---------------------------------------
* 日期：2014-01-20
* 作者：SJF0115
* 題目: 42.Trapping Rain Water
* 網址：https://oj.leetcode.com/problems/trapping-rain-water/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------*/
class Solution {
public:
//時間複雜度 O(n)，空間複雜度 O(1)
int trap(int A[], int n) {
// 最高的柱子，將數組分為兩半
int max = 0;
for (int i = 0; i < n; i++){
if (A[i] > A[max]) max = i;
}
int water = 0;
for (int i = 0, leftMaxHeight = 0; i < max; i++){
if (A[i] > leftMaxHeight){
leftMaxHeight = A[i];
}
else {
water += leftMaxHeight - A[i];
}
}
for (int i = n - 1, rightMaxHeight = 0; i > max; i--){
if (A[i] > rightMaxHeight){
rightMaxHeight = A[i];
}
else{
water += rightMaxHeight - A[i];
}
}
return water;
}
};
</pre><pre>
【代碼4】
/*---------------------------------------
* 日期：2014-01-20
* 作者：SJF0115
* 題目: 42.Trapping Rain Water
* 網址：https://oj.leetcode.com/problems/trapping-rain-water/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------*/
//第三種解法，用一個棧輔助，小於棧頂的元素壓入，大於等於棧頂就把棧裏所有小於或等於當
//前值的元素全部出棧處理掉。
// LeetCode, Trapping Rain Water
// 用一個棧輔助，小於棧頂的元素壓入，大於等於棧頂就把棧裏所有小於或
// 等於當前值的元素全部出棧處理掉，計算麵積，最後把當前元素入棧
// 時間複雜度 O(n)，空間複雜度 O(n)
class Solution {
public:
int trap(int a[], int n) {
stack<pair<int, int>> s;
int water = 0;
for (int i = 0; i < n; ++i) {
int height = 0;
// 將棧裏比當前元素矮或等高的元素全部處理掉
while (!s.empty()) {
int bar = s.top().first;
int pos = s.top().second;
// bar, height, a[i] 三者夾成的凹陷
water += (min(bar, a[i]) - height) * (i - pos - 1);
height = bar;
if (a[i] < bar) // 碰到了比當前元素高的，跳出循環
break;
else
s.pop(); // 彈出棧頂，因為該元素處理完了，不再需要了
}
s.push(make_pair(a[i], i));
}
return water;
}
};
類似題目：
[LeetCode]11.Container With Most Water
最後更新：2017-04-03 12:54:36