LeetCode 84. Largest Rectangle in Histogram

Description

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Explanation

In this approach, we use a stack to store indexes.

Initially, we push -1 onto the stack to mark the end. We start with the leftmost bar and keep pushing the current bar’s index onto the stack until we get two successive numbers in descending order.

Then we start popping the index numbers from the stack until heights[stack.peek()] ≤ heights[i]. Every time we pop, we find out the area of the rectangle: heights[stack.pop()] * (i − stack.peek() − 1).

Video Tutorial

Java Solution

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        
        for (int i = 0; i < heights.length; i++) {
            int currentBarHeight = heights[i];
            
            while (stack.peek() != -1 && currentBarHeight <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                
                int area = height * width;
                maxArea = Math.max(area, maxArea);
            }          
            
            stack.push(i);
        }
        
        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            
            int area = height * width;
            maxArea = Math.max(area, maxArea);
        }
        
        return maxArea;
        
        // Time complexity : O(n). n numbers are pushed and popped.
        // Space complexity : O(n). Stack is used.
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *