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!

C++:
01 int trapCal(int A[], int n, int p, int q)
02 {
03     int hight=A[p]<A[q]?A[p]:A[q];
04     int result=0;
05     for(int i=p+1;i<q;i++)
06     {
07         result+=hightA[i];
08     }
09     return result;
10 }
11 int trapHelper(int A[], int n, int p, int q)
12 {
13     if(p>=q1)
14         return 0;
15     int index1=0;
16     int max=-1;
17     for(int i=p;i<=q;i++)
18     {
19         if(A[i]>max)
20         {
21             max=A[i];
22             index1=i;
23         }
24     }
25     int index2=0;
26     max=-1;
27     for(int i=p;i<=q;i++)
28     {
29         if((i!=index1)&&(A[i]>max))
30         {
31             max=A[i];
32             index2=i;
33         }
34     }
35     int left=index1<index2?index1:index2;
36     int right=index1+index2left;
37     int part1=trapHelper(A,n,p,left);
38     int part2=trapCal(A,n,left,right);
39     int part3=trapHelper(A,n,right,q);
40     return part1+part2+part3;
41 }
42 class Solution {
43 public:
44     int trap(int A[], int n) {
45         // Start typing your C/C++ solution below
46         // DO NOT write int main() function
47         return trapHelper(A,n,0,n1);
48     }
49 };
Advertisements
This entry was posted in Divide and Conquer. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s