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.
思想：将装满水的面积减去没有装水的面积。
rain = water_sum - nowater_sum
有效地计算water_sum是本问题的关键。
2、一个区域的内能够承水是因为形成了由大到小再到大的凹坑。
定义 right_max[0--n-1]，用来保存从右往左搜索得到的最大值。如right_max[i]，表示在i这个柱子，右边的最高柱子值为right_max[i].
同理定义 left_max[0--n-1]
i柱子灌水后的区域面积为min(left_max[i], right_max[i]), 因为短板效应。
如此对0至n-1求此min(i)的和，便得到了water_sum，答案也就轻易得出了。代码如下。
主要思想在于把雨水的问题转化成有水无水的求差。
借助两个矩阵left_max, right_max 保存中间结果，巧妙地减少了许多计算量。
复制代码
#include "stdafx.h"
#include
using namespace std;
class Solution {
public:
int trap(int A[], int n);
// Accepted, O(n)
int Solution::trap(int A[], int n) {
// 注意极端情况的考虑哦！
if(n == 0) return 0;
int *right_max = new int[n];
int tmp_max = A[n-1];
right_max[n-1] = A[n-1];
// 没有水时的面积
int nowater_sum = A[n-1];
for(int i = n-2; i >= 0; --i) {
if(A[i] > tmp_max)
tmp_max = A[i];
right_max[i] = tmp_max;
nowater_sum += A[i];
}
int *left_max = new int[n];
tmp_max = A[0];
left_max[0] = A[0];
for(int i = 1; i < n; ++i) {
if(A[i] > tmp_max)
tmp_max = A[i];
left_max[i] = tmp_max;
}
// 计算有水时的面积
int water_sum = 0;
for(int i = 0; i < n; ++i) {
water_sum += min(left_max[i], right_max[i]);
}
delete []right_max;
delete []left_max;
return water_sum - nowater_sum;
}
int _tmain(int argc, _TCHAR* argv[])
{
int A[12] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Solution slu;
int result = slu.trap(A, 12);
return 0;
}