DSA & System Design

Largest Rectangle in Histogram

HardStacks and Monotonic Stacks

You are given an array heights describing a histogram: bar i has width 1 and height heights[i], and the bars stand side by side with no gaps.

Return the area of the largest rectangle that fits entirely inside the histogram. The rectangle is axis-aligned and may span several adjacent bars, but it can't be taller than the shortest bar it covers.

Constraints

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

Examples

Example 1

Input: heights = [2,4,5,1,3,3]
Output: 8

The bars of height 4 and 5 are side by side: a rectangle 2 wide and 4 tall has area 8.

Example 2

Input: heights = [3,3,3]
Output: 9

All bars are equal, so the whole histogram is one 3 × 3 rectangle.

Example 3

Input: heights = [2,0,2]
Output: 2

The 0 bar splits the histogram. Each side can only make a 1 × 2 rectangle.

JavaScript you'll use: Stacks, queues and deques Arrays: create, read, update

/**
 * @param {number[]} heights
 * @return {number}
 */
function largestRectangleArea(heights) {
  
}

Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.