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:

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

Leave a Reply

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