LeetCode-Trapping Rain Water解法
解法：（1）建立一个二维数组，记录各位置左侧最高点及右侧最高点，可通过O(n)计算得到。
（2）根据上述信息及当前高度，计算该点竖直方向能容纳多少水，仍是O（n）完成。
综上，渐近时间复杂度为O（n）；
class Solution {
public:
int trap(int A[], int n) {
if(n<=0)
return 0;
int* high=new int[n*2];
high[0*2+0]=0;
for(int i=1;i<n;i++){
if(A[i-1]>high[(i-1)*2+0])
high[i*2+0]=A[i-1];
else
high[i*2+0]=high[(i-1)*2+0];
}
high[(n-1)*2+1]=0;
for(int i=n-2;i>=0;i--){
if(A[i+1]>high[(i+1)*2+1])
high[i*2+1]=A[i+1];
else
high[i*2+1]=high[(i+1)*2+1];
}
int sum=0;
for(int i=0;i<n;i++){
int tmp=high[i*2+0]>high[i*2+1]?high[i*2+1]:high[i*2+0];
tmp=tmp-A[i];
if(tmp<0)
tmp=0;
sum+=tmp;
}
delete[] high;
return sum;
}
};
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
