84. Largest Rectangle in Histogram

Given bar heights of a histogram where each bar has width 1, return the area of the largest rectangle that fits inside it.

Keep indices of increasing heights on a stack. When a shorter bar arrives, every taller bar on the stack has found its right edge; its left edge is the index below it on the stack. Pop and measure.

1function largestRectangleArea(heights: number[]): number {
2  const stack: number[] = []; let best = 0;
3  for (let i = 0; i <= heights.length; i++) {
4    const h = i === heights.length ? 0 : heights[i];
5    while (stack.length && heights[stack.at(-1)!] > h) {
6      const top = stack.pop()!;
7      const left = stack.length ? stack.at(-1)! + 1 : 0;
8      best = Math.max(best, heights[top] * (i - left));
9    }
10    stack.push(i);
11  }
12  return best;
13}

best = 0

heights

stack (indices)

empty

Empty stack.

1 / 0

Space: play/pause · ←/→: step