首页 > 代码库 > Trapping Rain Water

Trapping Rain Water

2024-07-11 10:12:16   219人阅读

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!

 

[解题思路]
对于任何一个坐标，检查其左右的最大坐标，然后相减就是容积。所以，
1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
2. 从右往左扫描一遍，对于每一个坐标，求最大右值。
3. 再扫描一遍，求取容积并加和。
#2和#3可以合并成一个循环，

 

 1 class Solution { 2 public: 3     int trap(int A[], int n) { 4         if(n<3)return 0; 5         int res=0; 6         vector<int> maxL(n,0); 7         int maxtemp=A[0]; 8         maxL[0]=maxtemp; 9         for(int i=1;i<n;i++)10         {11             maxL[i]=maxtemp;12             if(A[i]>maxtemp)13             maxtemp=A[i];14         }15         vector<int> maxR(n,0);16         maxtemp=A[n-1];17         maxR[n-1]=maxtemp;18         for(int i=n-2;i>=0;i--)19         {20             maxR[i]=maxtemp;21             int vol=min(maxR[i],maxL[i])-A[i];22             if(vol>0)res+=vol;23             if(A[i]>maxtemp)24             maxtemp=A[i];25         }26         return res;27     }28 };

只用一个数组就可以了。

 1 class Solution { 2 public: 3     int trap(int A[], int n) { 4         if(n<3)return 0; 5         int res=0; 6         vector<int> maxL(n,0); 7         int maxtemp=A[0]; 8         maxL[0]=maxtemp; 9         for(int i=1;i<n;i++)10         {11             maxL[i]=maxtemp;12             if(A[i]>maxtemp)13             maxtemp=A[i];14         }15 16         maxtemp=A[n-1];17 18         for(int i=n-2;i>=0;i--)19         {20             int vol=min(maxtemp,maxL[i])-A[i];21             if(vol>0)res+=vol;22             if(A[i]>maxtemp)23             maxtemp=A[i];24         }25         return res;26     }27 };

 


联系
我们