Largest rectangle in a histogram

Find the biggest rectangle that fits under a histogram, using a monotonic stack of bar indices to size each bar's full width in one pass.

The idea

A bar can only stretch as a rectangle until it meets a shorter bar on either side. Walking left to right with a stack of increasing heights, a shorter bar forces every taller bar still on the stack to finally know its right edge, and the stack itself gives its left edge. A sentinel zero-height bar at the very end flushes out whatever remains.

Code

public static int LargestRectangleArea(int[] heights) {
    var stack = new Stack<int>(); // indices, heights increasing
    int best = 0;
    for (int i = 0; i <= heights.Length; i++) {
        int h = i == heights.Length ? 0 : heights[i];
        while (stack.Count > 0 && heights[stack.Peek()] >= h) {
            int top = stack.Pop();
            int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
            best = Math.Max(best, heights[top] * width);
        }
        stack.Push(i);
    }
    return best;
}

Tips

• The width of a popped bar is the gap between the new stack top and the current index, minus one.
• This is the same "pop until smaller" shape as next greater element, just using the gap between indices instead of a value.

In the .NET library

Without the sentinel pass at i == heights.Length, bars still on the stack when the array ends would never get measured. Pushing one extra height-0 bar handles that cleanly.