Leetcode 42. rainwater connection

Leetcode 42. Rainwater collection

subject

Given n Nonnegative integers indicate that each width is 1 Height map of columns of , Calculate columns arranged in this way , How much rain can be received after rain .

Ideas

• Double pointer solution
  Traverse all columns from the beginning , Except for the first element and the last element , For each element, calculate the highest element on the left and the highest element on the right of the column , And take the minimum , Subtract the height of the current column from this minimum , Is the height of rainwater that can be accumulated in this column .

• Dynamic programming

  • The highest left height of the current position is the highest left height of the previous position and the maximum value of the current height
  • The highest height on the right of the current position is the highest height on the right of the previous position and the maximum value of the current height

Code

• Double pointer solution

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int sum = 0;
        for(int i = 0; i < height.size(); i++)
        {
    
            //  The first pillar and the last pillar don't receive rain 
            if(i == 0 || i == height.size() - 1)
            {
    
                continue;
            }
            //  Record the highest columns on the left and right 
            int rheight = height[i];
            int lheight = height[i];

            for(int r = i + 1; r < height.size(); r++)
            {
    
                if(height[r] > rheight)
                {
    
                    rheight = height[r];//  Update maximum column 
                }
            }
            for(int l = i - 1; l >= 0; l--)
            {
    
                if(height[l] > lheight)
                {
    
                    lheight = height[l];
                }
            }

            int h = min(lheight,rheight) - height[i];
            
            if(h > 0)
            {
    
                sum += h;
            }

        }
        return sum;
    }
};

• Dynamic programming

class Solution {
    
public:
    int trap(vector<int>& height) {
    
       if(height.size() <= 2)
       {
    
           return 0;
       }

       vector<int> maxLeft(height.size(),0);
       vector<int> maxRight(height.size(),0);

       int size = maxRight.size();
       
       //  Record the maximum height of the left column of each column 
       maxLeft[0] = height[0];

       for(int i = 1; i < size; i++)
       {
    
           //  The maximum height on the left of the current position is the maximum value of the lag between the maximum height on the left of the previous position and this height 
           maxLeft[i] = max(height[i],maxLeft[i - 1]);
       }

       //  Record the maximum height of the right column of each column 
       maxRight[size - 1] = height[size - 1];//  First initialize to the height of the last column 
       //  Then push from the penultimate column 
       for(int i = size - 2; i >= 0; i--)
       {
    
           maxRight[i] = max(height[i],maxRight[i + 1]);
       }

       //  Sum up 
       int sum = 0;
       for(int i = 0; i < size;i++)
       {
    
           int count = min(maxRight[i],maxLeft[i]) - height[i];
           if(count > 0)
           {
    
               sum += count;
           }
       }
        return sum;
    }
};