Largest Rectangle in Histogram

Sliding Window Maximum

Longest Increasing Subsequence

Find the area of the largest rectangle that fits under a histogram.

Given an array of integers `heights` representing the histogram's bar heights where the width of each bar is `1`, return the area of the largest rectangle in the histogram.

## Example
```
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle is formed by the bars of height 5 and 6, giving area 5 * 2 = 10.
```

**Constraints**
- `1 <= heights.length <= 10^5`
- `0 <= heights[i] <= 10^4`

**Follow-up**
Why does appending a sentinel height of `0` avoid a separate cleanup pass after the main loop, and what would break if the sentinel were omitted?

- Each bar has width `1` and a given height.
- A rectangle spans a contiguous range of bars and its height is the **shortest** bar in that range.
- We want the maximum possible `height * width` over all ranges.

Understanding the Problem

- For each bar, imagine it is the limiting (shortest) bar of a rectangle.
- That rectangle stretches left and right until it meets a strictly shorter bar.
- If we know those left/right boundaries for every bar, the area is `height * (right - left - 1)`.

The Key Insight

- Keep a stack of bar indices whose heights are increasing.
- When the current bar is shorter than the bar on top of the stack, that top bar's rectangle must end here.
- Pop it, compute its area, and repeat until the stack is increasing again.

Using a Monotonic Stack

- After the loop, bars still on the stack never met a shorter bar to their right.
- Appending a sentinel height of `0` forces every remaining bar to be popped and measured.
- The width uses the array length as the right boundary.

Draining the Stack with a Sentinel

- Time: `O(n)` because each bar is pushed and popped exactly once.
- Space: `O(n)` for the stack.