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