Largest Rectangular Area in a Histogram | Set 2 | GeeksforGeeks

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

1) Create an empty stack.
2) Start from first bar, and do following for every bar ‘hist[i]‘ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.
For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done.
We have a stack, and push into it the indices of the bars one by one. But before the push, we pop out the indices of the bars (if any) that are higher than the one under investigation. Upon each pop, we calculate the area of largest rectangle containing the popped bar as follows: if the stack is empty, it means all previous bars are all higher than it, so the area to be calculated would be the product of its height and the number of the bars including and before it; otherwise, it means the heights of the bars between the one in the top of the stack and the one under investigation (both exclusive) are no smaller than that of the popped one, so the area would be the product of its height and the number of those bars.
Time: O(n) code from http://www.darrensunny.me/leetcode-largest-rectangle-in-histogram/

public int largestRectangleArea(int[] height) {

        if (height == null || height.length == 0)

            return 0;

        int n = height.length;

        int largestArea = 0;

        Deque<Integer> indexStack = new LinkedList<Integer>();

 

        // For each bar, pop out the bars higher than it and calculate the largest area of

        // the rectangle using this full bar, before pushing it to the stack

        for (int i = 0; i < n; i++) {

            while (!indexStack.isEmpty() && height[i] <= height[indexStack.peek()]) {

                int index = indexStack.pop();

                if (indexStack.isEmpty())

                    largestArea = Math.max(largestArea, i*height[index]);

                else

                    largestArea = Math.max(largestArea, (i-indexStack.peek()-1)*height[index]);

            }

            indexStack.push(i);

        }

 

        // Calculate the largest area of the rectangle using each full bar remaining in the stack

        while (!indexStack.isEmpty()) {

            int index = indexStack.pop();

            if (indexStack.isEmpty())

                largestArea = Math.max(largestArea, n*height[index]);

            else

                largestArea = Math.max(largestArea, (n-indexStack.peek()-1)*height[index]);

        }

 

        return largestArea;

    }

Read full article from Largest Rectangular Area in a Histogram | Set 2 | GeeksforGeeks