leetcode 42. Trapping Rain Water-蒲公英云

leetcode 42. Trapping Rain Water

灰太狼 2022-07-28 04:13 229阅读 0赞

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!

int trap(int* height, int heightSize) {
    if(height==NULL)
        return 0;
    if (heightSize < 3)
        return 0;
    int k = 1, watersum = 0;
    while (k < heightSize-1)
    {
        if (height[k] < height[k - 1])
        {
            int kk = k + 1;
            int endhigh = height[k], endptr=-1;
            while (kk < heightSize&&height[kk] < height[k - 1])
            {
                if (height[kk] > endhigh)
                {
                    endptr = kk;
                    endhigh = height[kk];
                }
                kk++;
            }
            if (kk == heightSize)
            {
                if (endptr > 0)
                {
                    for (int i = k; i < endptr; i++)
                        watersum += height[endptr] - height[i];
                    k = endptr+1;
                }
                else
                    k++;
            }
            else
            {
                for (int i = k; i < kk; i++)
                    watersum += height[k - 1] - height[i];
                k = kk+1;
            }
        }
        else
            k++;
    }
    return watersum;
}