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!

This is actually a simple question, the water that each bar can trap above it depends on the left and right highest bar, so use dp to calculate these two from left to right and from right to left. Actually we can just calculate

public class Solution {
    public int trap(int[] A) {
        if (A.length < 3)
            return 0; // two bars can not trap water
        int [] leftMax = new int [A.length];
        leftMax[0] = 0;
        int currMax = A[0];
        for (int i = 1; i < A.length; i++) {
            leftMax[i] = currMax;
            currMax = Math.max(currMax, A[i]);
        }
        //find right max and calculate the trapped water
        currMax = A[A.length - 1];
        int total = 0;
        for (int i = A.length - 1; i>0; i--) {
            if (A[i] < leftMax[i] && A[i] < currMax) {
                total += Math.min(leftMax[i], currMax) - A[i];
            }
            currMax = Math.max(currMax, A[i]);
        }
        return total;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s