O(n) Java solution using stack


  • 1

    This question is mind-challenging. O(n^2) solution is easier but might TLE.
    The key to understand this method is that for a height at a specific index, what is the safe region in which that height is the min and define the area. Notice we are storing index into stack, since we can always get height through index. We only push index into stack if its corresponding height is higher than the peek 's height. So each time when we meet with the condition of pop(), we are sure the index popped out will have the min height from it to the origin peek before popping.

    public class Solution {
    public int largestRectangleArea(int[] height) {
        if(height == null || height.length == 0 )
            return 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int res = 0;
        int i;
        for(i=0; i<height.length; i++){
            while(!stack.isEmpty() && height[stack.peek()] >= height[i]){
                int index = stack.pop();
                int temp = stack.isEmpty() ? i*height[index] :  ( (i - 1) - (stack.peek() + 1) +1 ) *height[index];
                res = Math.max(res,temp);
            }
            stack.push(i);    
        }
        
        while(!stack.isEmpty()){
            int index = stack.pop();
            int temp = stack.isEmpty() ? i * height[index] : ( i - stack.peek() -1 ) * height[index];
            res = Math.max(res,temp);
        }
        return res;
    }
    

    }


Log in to reply
 

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