Histogram - Implementation

Here's the solution:

function largestRectangleArea(heights)
    n := length of heights
    stack := empty stack // stores indices
    maxArea := 0

    for i from 0 to n - 1
        while stack is not empty and heights[i] < heights[top of stack]
            j := pop from stack
            if stack is empty
                left := -1
            else
                left := top of stack
            width := i - left - 1
            area := heights[j] × width
            maxArea := max(maxArea, area)
        push i onto stack

    // Pop remaining bars
    while stack is not empty
        j := pop from stack
        if stack is empty
            left := -1
        else
            left := top of stack
        width := n - left - 1
        area := heights[j] × width
        maxArea := max(maxArea, area)

    return maxArea

Time: $O(n)$. Space: $O(n)$.