【leetcode】 Trapping Rain Water

地址

https://leetcode.com/problems/trapping-rain-water/description/

题目

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!

思路

假如从i开始,找到后面第一个大于等于h[i]的数,然后计算答案。如何后面没有大于等于h[i]的数,那么就找到i后面最大的一个数,计算答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int trap(vector<int>& h) {
if(h.size()==0)
return 0;
int n=h.size(),ans=0,pre[100000];
pre[0]=h[0];
for(int i=1;i<n;i++) pre[i]=pre[i-1]+h[i];
for(int i=0;i<n-1;i++)
if(h[i])
{
int d=-1,dh,ff=0;
for(int j=i+1;j<n;j++)
if(h[j]>=h[i])
{
ans+=min(h[i],h[j])*(j-i-1)-(pre[j-1]-pre[i]);
i=j-1,ff=1;
break;
}
else if(d<0||h[j]>dh)
d=j,dh=h[j];
if(d>0&&!ff)
ans+=dh*(d-i-1)-(pre[d-1]-pre[i]),i=d-1;
}
return ans;
}
};