Largest Rectangle in Histogram Cont…

Question: Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

You may read the full question here.

Approach 3: Continuing from where we left off. Umm... Let me be honest and tell you this — some incredibly smart people/person came up with this brilliant solution using Stack. And it took a while for me to get a hang of things. Finally, found some good resources that helped me understand the idea — 1) this video and 2) this post.

The key take away is that every element in the array is pushed only once, and every element in the stack is eventually popped. Thus, the run time is effectively O(n).

Although redundant, here is the code for this algorithm —

//Approach 3:
//Runtime: 13ms
//Memory usage: 38.7MB
class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        Stack<Integer> stack = new Stack();
        int i = 0;
        while(i<heights.length){
            if(stack.isEmpty() || heights[i]>=heights[stack.peek()]){
                stack.push(i);
                i++;
            } else {
                int top = stack.pop();
                int area = heights[top] * (stack.isEmpty()? i : (i-stack.peek()-1));
                max = Math.max(max, area);
            }
        }
        while(!stack.isEmpty()) {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty()? i : (i-stack.peek()-1));
            max = Math.max(max, area);
        }
        return max;
    }
}

Find more posts here.

Cheers & Chao!