84. 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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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

Output: 10

Solutions

Solution 1

/**
 * Time complexity : O(n^2). Every possible pair is considered.
 * Space complexity : O(1). No extra space is used.
 */

 public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minheight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minheight = Math.min(minheight, heights[j]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}

Solution 2

/**
 * Time complexity : O(n). nn numbers are pushed and popped.
 * Space complexity : O(n). Stack is used.
 */

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) return 0;
        
        Stack<Integer> stack = new Stack<>();
        int i = 0, area = 0;
        
        while(i < heights.length) {
            if(stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.add(i++);
            } else {
                area = Math.max(area, calculateArea(stack, heights, i));
            }
        }
        
        while(!stack.isEmpty()) {
            area = Math.max(area, calculateArea(stack, heights, i));
        }
        
        return area;
    }

    private int calculateArea(Stack<Integer> stack, int[] heights, int i) {
        int top = stack.pop();
        int height = heights[top];
        int weight = (stack.isEmpty())? i: (i-stack.peek()-1);
        return height * weight;
    }
}

Follow up