O(n) Memory and O(n) time
class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) return 0; int[] left = new int[n]; int[] right = new int[n]; left[0] = height[0]; right[n - 1] = height[n - 1]; int j; for (int i = 1; i < n; i++) { left[i] = Math.max(left[i - 1], height[i]); right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]); } int area = 0; for (int i = 1; i < n - 1; i++) { area += Math.min(left[i], right[i]) - height[i]; } return area; } }