80. Largest Rectangle in Histogram

HardStack

Given an array of integers `heights` where `heights[i]` represents the height of a bar in a histogram (each bar has width 1), find the area of the largest rectangle that can be formed within the histogram. The rectangle must be made up of contiguous bars. For example, given heights = [2,1,5,6,2,3], the largest rectangle has area 10 (formed by the bars at indices 2 and 3 with heights 5 and 6, spanning width 2 at minimum height 5).

Examples

Input: [2,1,5,6,2,3]

Output: 10

Explanation: The largest rectangle spans indices 2-3 (heights 5,6) with min height 5 and width 2, giving area 10.

Constraints

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

Run checks all cases above. Submit evaluates all test cases.