O(n) space and time

```
public class Solution {
public int trap(int[] height) {
int[] max = new int[height.length];
if(height==null || height.length==0){
return 0;
}
max[height.length-1]=height[height.length-1];
for(int i=max.length-2; i>=0; i--){
max[i]=max[i+1]>height[i+1]?max[i+1]:height[i+1];
}
int maxsofar=height[0]>max[0]?max[0]:height[0];
int sum=0;
for(int i=1; i<height.length; i++){
if(height[i]>maxsofar || maxsofar>max[i]){
maxsofar=height[i]>max[i]?max[i]:height[i];
continue;
}
if(height[i]<maxsofar && height[i]!=max[i]){
sum+=maxsofar-height[i];
}
}
return sum;
}
}
```