84. Largest Rectangle in Histogram
You're given an integer array heights where heights[i] is the height of the i-th bar of a histogram. All bars have width 1 and stand side by side on a common baseline.
Return the area of the largest axis-aligned rectangle that fits entirely inside the histogram. Equivalently: pick any contiguous block of bars — the rectangle you can inscribe over that block has the block's width and the height of its shortest bar, so you want to maximize width × min height over all blocks.
Example 1:
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The bars of height 5 and 6 support a rectangle of height 5 and width 2, area 10 — nothing larger fits anywhere else.
Example 2:
Input: heights = [2, 4]
Output: 4
Explanation: Candidates: the single height-4 bar (area 4), the single height-2 bar (area 2), or both bars at height 2 (area 4). The best is 4.
Constraints:
- 1 ≤ heights.length ≤ 10⁵
- 0 ≤ heights[i] ≤ 10⁴
Hints:
Every optimal rectangle is as tall as some bar — its height equals `heights[i]` for at least one bar `i` inside it (otherwise you could grow it upward). So it's enough to answer, for each bar: how far can a rectangle of exactly this bar's height stretch left and right?
Bar `i`'s rectangle is blocked by the nearest bar strictly shorter than `heights[i]` on each side. Brute-forcing those boundaries per bar is O(n²); the question is how to find all of them in one sweep.
Sweep left to right keeping a stack of bar indices with increasing heights. When the current bar is shorter than the stack top, the top bar's right boundary is the current index — pop it and settle its area; its left boundary is whatever remains below it on the stack. A sentinel height 0 appended at the end flushes everything.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: heights = [2, 1, 5, 6, 2, 3]
Expected output: 10