Description

LeetCode 84

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

Analysis

The objective is to find the maximum rectangle. So consider about this problem first. How can we get a potential ideal rectangle? In fact, this kind of rectangle must satisfy that the minimum bar inside the rectangle is larger than the past bar and the next bar of the rectangle.

To implement this in an efficient way, we use a stack. Because if we consider about the problem’s feature, we can find we need to visit one element again after first time to visit it. In the process, push the element one by one to the element. But if the element is not empty and the element is less than the top of the stack, pop the stack until the top of the element is not less than the top of the stack, which can ensure we get the potential rectangles. And we should update the result at each step of poping the stack. A point that should be considered is that after pushing all the elements into the stack, we should compare the top of stack with zero, the minimum element in this problem, which will make the stack begin being poped.

The time and space are both \(O(n)\).

Solution

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> s=new Stack<>();
        int res=0;
        int temp,tempi,start;
        for(int i=0;i<=heights.length;i++)
        {
            if(i==heights.length)
                temp=0;
            else
                temp=heights[i];
            while(s.size()!=0&&temp<heights[s.peek()])
            {
                tempi=s.pop();
                start=s.size()==0?-1:s.peek();
                res=Math.max(res,heights[tempi]*(i-start-1));
            }
            s.push(i);
        }
        return res;
    }
}

Reference

[1] https://www.geeksforgeeks.org/largest-rectangle-under-histogram/

1 Comment

Leave a Reply

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