Stack Topological Sort Simulation
Proficient Level

Implement the largestRectangleHistogram method that returns the largest rectangle area possible in a histogram.

The input contains an array heights and its length size. Each value represents the height of one bar in a histogram, and every bar has width 1.

Your task is to find the largest possible rectangle area that can be formed using one or more adjacent bars.

For example, for [2,1,5,6,2,3], the largest rectangle area is 10.

Example 1
Input:
heights (int[]) = [2,1,5,6,2,3]
size (int) = 6
Return:
(int) 10
Example 2
Input:
heights (int[]) = [2,4]
size (int) = 2
Return:
(int) 4
Example 3
Input:
heights (int[]) = [1,1,1]
size (int) = 3
Return:
(int) 3

Use a monotonic increasing stack of bar indexes.

The stack keeps bars in increasing height order. When a shorter bar is found, it means the taller bars on the stack cannot extend further to the right, so their maximum rectangle area can be calculated.

For each popped bar, use its height and the width between the previous smaller bar and the current index. Add a sentinel height 0 at the end to force all remaining bars to be processed.

Pseudocode:

function largestRectangleHistogram(heights, size):
    stack = empty stack of indexes
    best = 0
    for i from 0 to size:
        if i == size:
            currentHeight = 0
        else:
            currentHeight = heights[i]
        while stack is not empty and currentHeight < heights[top of stack]:
            heightIndex = pop from stack
            height = heights[heightIndex]
            if stack is empty:
                width = i
            else:
                width = i - top of stack - 1
            best = maximum(best, height * width)
        push i into stack
    return best
Run your code to see the result.