Largest Rectangle in Histogram

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

Example:

• Input: [2, 1, 5, 6, 2, 3]
• Output: 10 (The rectangle from index 2 to 3 with height 5 has area 5 * 2 = 10).

We use a Monotonic Increasing Stack.

Core Idea:
For each bar h at index i, if we know the first bar to the left that is smaller (left_limit) and the first bar to the right that is smaller (right_limit), then the maximum width for a rectangle with height h is right_limit - left_limit - 1.

One-Pass Logic:

1. Maintain a stack of indices with increasing heights.
2. When we encounter a bar h[i] smaller than h[stack.top()], it means h[i] is the Right Limit for h[stack.top()].
3. Pop top. Now the New Top of the stack is the Left Limit for the popped bar.
4. Calc Area: height * (i - stack.top() - 1).
5. Repeat until stack rule is satisfied, then push i.