Compute Maximum Area Under Adjacent Bars

You are given an array heights of n non-negative integers. Each value represents the height of a vertical bar of width 1, and the bars are placed next to each other.

Choose any contiguous range of bars. Within that range, you may form a rectangle whose height is at most the minimum bar height in the range and whose width is the number of bars in the range. Return the maximum possible rectangle area.

Constraints:

• 1 <= n <= 100000
• 0 <= heights[i] <= 1000000000
• The answer may require 64-bit integer arithmetic.

Example:

• Input: heights = [2, 1, 5, 6, 2, 3]
• Output: 10
• Explanation: Choosing the bars with heights 5 and 6 gives height 5, width 2, and area 10.

Compute Maximum Area Under Adjacent Bars

You are given an array heights of n non-negative integers. Each value represents the height of a vertical bar of width 1, and the bars are placed next to each other.

Choose any contiguous range of bars. Within that range, you may form a rectangle whose height is at most the minimum bar height in the range and whose width is the number of bars in the range. Return the maximum possible rectangle area.

This is the classic "Largest Rectangle in Histogram" problem. A monotonic stack of indices lets you find, for each bar, the maximal contiguous span over which that bar is the limiting (minimum) height, in O(n) total time.

Example:

• Input: heights = [2, 1, 5, 6, 2, 3]
• Output: 10
• Explanation: Choosing the bars with heights 5 and 6 gives height 5, width 2, and area 10.

Hints

1. For each bar, ask: what is the widest contiguous span in which this bar is the shortest? Its height times that width is a candidate area.
2. Use a stack that holds bar indices in non-decreasing height order. When the current bar is shorter than the bar on top of the stack, that top bar can no longer extend rightward — pop it and compute its area.
3. When popping index top, the rectangle height is heights[top]; its left boundary is the new stack top (after popping) and its right boundary is the current index i, so width = i - stack[-1] - 1 (or i if the stack is empty).
4. Append a sentinel bar of height 0 at the end (iterate to index n) so every remaining bar in the stack gets flushed and measured.