题目

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个非负整数，代表一个高度地图，计算最大的存水量，以上图为例，可以看出存水量为6。
首先从左向右依次寻找比当前高度h1更高的地方h2，如果找到，那么存水量即可按当前高度进行存水。之后以h2再向后寻找更高的地方h3,直到最后位置，发现当找到最高的h4位置后，之后就需要以更低的位置进行存水量，但是不确定啥时候，所以换个思路。
在以上面的思路从右向左计算一遍，但是要注意计算到h4位置为止，因为可能会遇到对称等情况。当时做的时候遇到好几次错误，以下给出一些易错的数据，供测试。

/*
[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;
}