題目
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.
分析
給出N個非負(fù)整數(shù)区赵，代表一個高度地圖，計算最大的存水量，以上圖為例摔踱，可以看出存水量為6。
首先從左向右依次尋找比當(dāng)前高度h1更高的地方h2膀息，如果找到，那么存水量即可按當(dāng)前高度進(jìn)行存水冗酿。之后以h2再向后尋找更高的地方h3,直到最后位置，發(fā)現(xiàn)當(dāng)找到最高的h4位置后襟沮，之后就需要以更低的位置進(jìn)行存水量，但是不確定啥時候，所以換個思路巫玻。
在以上面的思路從右向左計算一遍，但是要注意計算到h4位置為止诗力，因為可能會遇到對稱等情況屿良。當(dāng)時做的時候遇到好幾次錯誤尘惧，以下給出一些易錯的數(shù)據(jù)，供測試。
/*
[5,5,1,7,1,1,5,2,7,6]
[9,2,9,3,2,2,1,4,8]
[4,2,3]
[2,0,2]
[0,1,2,3,6]
[1,2,3,4,5]
[0,1,3,5,7,3,8,6,3,0,1,2]
*/
int trap(int* height, int heightSize) {
int p=0,p1=0,ans=0;//所有存水量
int temp=0;//一段高度值
while(height[p]==0&&p<heightSize)
p++;
if(p==heightSize)
return 0;
p1=p;
int h=height[p];
//正向依次計算，直到最高點
for(int i=p+1;i<heightSize;i++)
{
if(height[i]>=h)
{
//if(height[i]>h)flag=1;
ans=ans+(i-p1-1)*h-temp;
temp=0;
h=height[i];
p1=i;
}
else
{
temp=temp+height[i];
}
//printf("%d %d %d %d\n",i,h,temp,ans);
}
//反向依次計算嚼蚀，直到最高點
temp=0;
p=heightSize-1;
while(p>0&&height[p]==0)
p--;
h=height[p];
for(int i=p-1;i>=p1;i--)
{
if(height[i]>=h)
{
ans=ans+(p-i-1)*h-temp;
temp=0;
h=height[i];
p=i;
}
else
temp=temp+height[i];
//printf("%d %d %d %d\n",i,h,temp,ans);
}
return ans;
}
