The water each bar can trap depends on the maximum height on its left and right. Thus scan twice - from left to right, and right to left and record the max height in each direction. The third time calculate the min difference between left/right height and current bar height. Sum the trapped water to get the final result.
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int ans = 0;
for (int i = 0; i < height.length; i++) {
int leftMax = 0;
int rightMax = 0;
int j = i - 1;
int k = i + 1;
int waterHeight = 0;
while (j >= 0) {
leftMax = Math.max(height[j], leftMax);
j--;
}
while (k < height.length) {
rightMax = Math.max(height[k], rightMax);
k++;
}
waterHeight = Math.min(leftMax, rightMax);
ans += Math.max(waterHeight - height[i], 0);
}
return ans;
}
}
Dynamic Programming
public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] heights) {
if (heights == null || heights.length < 3) {
return 0;
}
int length = heights.length;
int[] left = new int[length];
int[] right = new int[length];
int trapped = 0;
// For heights[0] or heights[length - 1], the max left/right height is 0
left[0] = 0;
right[length - 1] = 0;
// Keep track of the max height on the left of height[i]
for (int i = 1; i < length; i++) {
left[i] = Math.max(left[i - 1], heights[i - 1]);
}
// Keep track of the max height on the right of height[i]
for (int j = length - 2; j >= 0; j--) {
right[j] = Math.max(right[j + 1], heights[j + 1]);
}
// Calculate the total trapped water
for (int k = 0; k < length; k++) {
trapped += Math.max(Math.min(left[k], right[k]) - heights[k], 0);
}
return trapped;
}
}
Two Pointers
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int leftMax = 0, rightMax = 0;
int left = 0, right = height.length - 1;
int trapped = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
trapped += Math.max(leftMax - height[left], 0);
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
trapped += Math.max(rightMax - height[right], 0);
}
right--;
}
}
return trapped;
}
}
Monotonic Stack
class Solution {
public int trap(int[] height) {
int n = height.length;
Stack<Integer> stk = new Stack<>();
int res = 0;
for (int i = 0; i < n; i++) {
if (stk.isEmpty() || height[i] < height[stk.peek()]) {
stk.push(i);
} else {
while (!stk.isEmpty() && height[i] >= height[stk.peek()]) {
int h = height[stk.pop()];
if (!stk.isEmpty()) {
int len = i - stk.peek() - 1;
res += (Math.min(height[i], height[stk.peek()]) - h) * len;
}
}
stk.push(i);
}
}
return res;
}
}
