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.

**Example:**

Input:[0,1,0,2,1,0,1,3,2,1,2,1]Output:6

## Solution

public int trap(int[] height) { if (height == null || height.length == 0) { return 0; } int result = 0; // leftMax represents the highest bar from left int leftMax = Integer.MIN_VALUE; // rightMax represents the highest bar from right int rightMax = Integer.MIN_VALUE; // use two pointers to scan the entire array until they meet with each other // Key points: any bars in the middle of leftMax bar and rightMax bar will not influence // how much water can current position trap for (int left = 0, right = height.length - 1; left <= right;) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); //how much can current position trap depends on the shorter bar if (leftMax < rightMax) { //DO NOT FORGET to subtract bar height of current position result += leftMax - height[left]; left++; } else { result += rightMax - height[right]; right--; } } return result; }