Different idea from Histogram O(n) Java solution -> and <-


  • 0
    S

    Let me use an example to illustrate my idea.

    A[] = [0,1,0,2,1,0,1,3,2,1,2,1] as the question shows.
    Go through the entire sequence. I am gonna note down the largest bar I've met so far, which is 1, and then each time I encounter a non-zero integer, which is smaller than 1, I gonna push it to stack (actually it could be queue or anything). Each time I encounter a non-zero integer but greater or equal to 1, I gonna start counting rain drops and set the largest bar as this new bar. The reason why I can start counting rain drops is that if meet a new bar greater than my previous largest bar, the bars afterwards won't change the total rain drops it collect before this new bar.

    To count the rain drop is quite easy. Look at this:

          =

    =    =

    ==  =

    ====

    3 2 1 4

    The total rain drop it collects is 3 *(total_length) - 2 - 1.

    Just subtract the small bars in between!

    Then doing the whole process would bring the rain drop counting stop at the largest bar in the sequence. Yes. My algorithm is actually finding the largest bar, collect both sides. So, reverse the rest bar, which lies in the other side of the largest bar and doing the same on it.

    public class Solution {
        public int trap(int[] A) {
            int largest_pre = -1;
    	        int rain = 0;
    	        int i = 0;
    	        Stack<Integer> stack = new Stack<Integer>();
    	        while(i < A.length){
    	            if(A[i] != 0){
    	                if(stack.isEmpty()){
    	                    stack.push(i);
    	                    largest_pre = i;
    	                }else{
    	                    if(A[i] < A[largest_pre]){
    	                        stack.push(i);
    	                    }else{
    	                        rain += (i-largest_pre)*A[largest_pre];
    	                        while(!stack.isEmpty())
    	                            rain -= A[stack.pop()];
    	                        largest_pre = i;
    	                        stack.push(i);
    	                    }
    	                }
    	            }
    	            i++;
    	        }
    	        
    	        // for the rest, reverse it and do the same
    	        if(stack.size()>1){
    	            int rest[] = new int[A.length-largest_pre];
    	            for(i = 0;i < rest.length;i++)
    	                rest[i] = A[A.length-1-i];
    	            rain += trap(rest);
    	        }
    	        
    	        return rain;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.