Simple Java code with O(n) running time. 2 pass


  • 0
    A

    The idea is that :

    1. if the current height is smaller than current max, push it into stack
    2. each time we found a new max height, it will hold water with original max height. so the MaxWater is:
    while(!stack.isEmpty())
        MaxWater += original max height - stack.pop();
    

    My original solution only has one pass, from left to right. However, I found that after it reaches the max Height of the whole array, the max water will not increase any more. So I do the same job again from right to left until it reaches the max height which we already knew.

    public class Solution {
        public int trap(int[] height) {
            if(height.length==0)
                return 0;
            
            Stack<Integer> stackL = new Stack<Integer>();
            Stack<Integer> stackR = new Stack<Integer>();
            int maxWater = 0;
            int left = 0, right = height.length-1;
            int lMax = 0, rMax = 0;
            
            while(left<height.length){
                if(height[left]<lMax)
                    stackL.push(height[left]);
                else {
                    while(!stackL.isEmpty())
                        maxWater += lMax - stackL.pop();
                    lMax = height[left];
                }
                left++;
            }
            
            while(rMax<lMax){
                if(height[right]<rMax)
                    stackR.push(height[right]);
                else{
                    while(!stackR.isEmpty())
                        maxWater += rMax - stackR.pop();
                    rMax = height[right];
                }
                right--;
            }
            
            return maxWater;
        }
    }
    

Log in to reply
 

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