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;
}
}

### Like this:

Like Loading...

*Related*