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!
[解题思路]
对于任何一个坐标,检查其左右的最大坐标,然后相减就是容积。所以,
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 };
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。