[LeetCode]042-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!
Solution:アイデアは、まず最高のポイントを見つけて、両側で処理します.例えば左の場合:2つのポインタi,jを設定します.i中間最高点に移動し、height[i]>=height[j]の場合.jとiの間の格納可能な空間を計算し、jをiの位置:j=iに移動し、iは最高点まで後方に移動し続ける.右側の処理は似ています.コードは次のとおりです.

class Solution {
public:
    int trap(vector<int>& height)
    {
        int n = height.size();
        int i,j,k;
        int sum = 0;
        int h = 0;
        int max = 0;
        for(i =0;i<n;i++)
        {
            if(height[i] > max)
            {
                max = height[i];
                h = i;
            }
        }
        i = 0;
        j = i+1;
        while(i<=h && j <=h)
        {
            if(height[i] >=  height[j])
            {
                sum += calculate(height,j,i);
                j = i;
            }
            i++;
        }
        j=n-1;
        i = j-1;
        while(i >= h)
        {
            if(height[i] >=  height[j])
            {
                sum += calculate(height,i,j);
                j = i;
            }
            i--;
        }
        return sum;
    }
    int calculate(vector<int> height,int begin,int end)
    {
        int h = min(height[begin],height[end]);
        int w = end - begin-1;
        int area = h * w;
        for(int i = begin+1;i<end;i++)
        {
            area -= height[i];
        }

        return area<0?0:area;
    }
};