首页 > itarticle > trapping rain water

trapping rain water

admin 11月 11, 2020 0

Problem:

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!

Leetcode link
Lintcode link

My solution:

For each bar, find the highest bars of the left side and right side respectively.
The trapping water for the bar is min(leftMax,rightmax) - its height.

There are two solutions.

- Find the highest bar
- Process the left and right of the highest bar respectively
- Go through the bars from left to right, calculate the left highest bar for each bar
- Go through the bars form right to left, calculate the left highest bar for each bar
- Calculate the min(leftMax,rightmax) - its height for each bar.


	> File Name: TrappingWater.java
	> Author: Yao Zhang 
	> Mail: [email protected] 
	> Created Time: Fri 13 Nov 10:45:30 2015
 ************************************************************************/

public class {
    // Solution 1
    public int trap(int[] height){
        int area = 0;
        int maxIndex = 0;
        
        // Find the index of the highest bar
        for (int i = 0; i < height.length; i ++){
            if (height[i] > height[maxIndex])
                maxIndex = i;
        }
        
        // Process the left side of the highest bar
        int leftMax = 0;
        for (int i = 0; i < maxIndex; i++){
            if (height[i] > leftMax) 
                leftMax = height[i]; 
            else
                area += leftMax - height[i];
        }

        // Process the rigtht side of the highest bar
        int rightMax = 0;
        for (int i = height.length - 1; i > maxIndex; i--){
            if (height[i] > rightMax) 
                rightMax = height[i]; 
            else
                area += rightMax - height[i];
        }

        return area;
    }

    // Solution 2
    public int trap2(int[] height){
        int area = 0;

        if (height.length == 0)
            return area;

        // find the left highest bar value for each bar
        int[] leftMax = new int[height.length];
        leftMax[0] = 0;
        for (int i = 1; i < height.length; i++){
           leftMax[i] = Math.max(height[i-1], leftMax[i-1]) ;
        }

        // for each bar, calculate the trapping water by 
        // calculating min(leftMax,rightmax) - height
        int max = 0;
        for (int i = height.length - 1; i > 0; i--){
            int diff = Math.min(max,leftMax[i]) - height[i];
            area += diff > 0 ? diff : 0;
            max = Math.max(height[i], max);
        }

        return area;
    }
}