I found two solutions in the discuss. Both of them are O(n) time complexity. The first one got TLE but the second one got AC. Can anyone explain on why the second solution is faster than the first one?

First Solution:

```
public int trap(int[] height) {
if(height == null || height.length<3){ return 0;}
int low= 0, high= height.length-1;
int maxLeft= 0, maxRight=0;
int res= 0;
while(low <= high){
maxLeft= Math.max(maxLeft, height[low]);
maxRight= Math.max(maxRight, height[high]);
if(maxLeft < maxRight){
res+= (maxLeft - height[low]);
low++;
}else{ //maxLeft > maxRight
res+= (maxRight - height[high]);
high--;
}
}
return res;
}
```

Second Solution (dp):

```
public int trap(int[] height) {
int len = height.length;
if(len == 0) return 0;
int[] maxleft = new int[len];
int[] maxright = new int[len];
int max = Integer.MIN_VALUE;
for(int i=0;i<len;i++){
if(height[i] > max){
max = height[i];
}
maxleft[i] = max;
}
max = Integer.MIN_VALUE;
for(int i=len-1;i>=0;i--){
if(height[i] > max){
max = height[i];
}
maxright[i] = max;
}
int ret = 0;
for(int i=0;i<len;i++){
int diff = Math.min(maxleft[i],maxright[i]) - height[i];
if(diff > 0) ret += diff;
}
return ret;
}
```