Trapping Rain Water

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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Naive Way: Let me start from the begin, when I met some bar that is no less than current bar, I am able to determine how much water can trap from current bar to that some bar. Better use a stack to keep track of bars that are smaller than current bar.

Run time is One Pass, O(n). Space is O(n).

 public class Solution {  
   public int trap(int[] A) {  
     Stack<Integer> stack = new Stack<Integer>();  
     int sum = 0;  
     int pre = 0;  
     int i = -1;  
     while(++i < A.length){  
       if(A[i]==0){pre = 0;continue;}  
       while(!stack.isEmpty() && A[i] >= A[stack.peek()]){  
         sum += (A[stack.peek()] - pre) * (i-stack.peek()-1);  
         pre = A[stack.pop()];  
       }  
       if(!stack.isEmpty()){  
         sum += (A[i] - pre) * (i-stack.peek()-1);  
         pre = A[i];  
       }  
       stack.push(i);  
     }  
     return sum;  
   }  
 }  

Improved Way: Is there a way to make the space O(1)? Based on my previous code, the stack is not replaceable. So I cannot make up an O(1) algorithm with the stack.

Consider the bars as a whole, only the left most and right most bars will become boundaries/walls. Anything in between will take the unit place of water. This is a thinking. Let me give it a try.

The following algorithm is the implementation of my idea. Track from both ends to middle, keep increase the boundary bar, while deleting any lower bar in the middle.

 public class Solution {  
   public int trap(int[] A) {  
     int left = 0 , right = A.length-1;  
     int sum = 0;  
     int pre = 0;  
     while(left < right){  
       sum += (Math.min(A[left], A[right])-pre) * (right-left-1);  
       pre = Math.min(A[left],A[right]);  
       if(A[left] > A[right]){   
         int temp = right-1;  
         while(left < temp && A[temp] <= pre){sum-=A[temp];temp--;}  
         if(left < temp) sum -= pre;  
         right = temp;  
       }else{  
         int temp = left+1;  
         while(temp < right && A[temp] <= pre){sum-=A[temp];temp++;}  
         if(temp < right) sum -= pre;  
         left = temp;  
       }  
     }  
     return sum;  
   }  
 }  

There is a much more concise implementation java-10-lines-accepted-code-time-space-there-better-solution