Monotonic Stack — Keep Order in the Stack

A monotonic stack keeps values (or indices) strictly increasing or decreasing; each push may pop many, but each item enters and leaves once overall.

Try this in Python

def largest_rectangle_hist(heights: list[int]) -> int:
    st: list[int] = []
    best = 0
    heights = heights + [0]
    for i, h in enumerate(heights):
        while st and heights[st[-1]] > h:
            height = heights[st.pop()]
            left = st[-1] + 1 if st else 0
            best = max(best, height * (i - left))
        st.append(i)
    return best


print(largest_rectangle_hist([2, 1, 5, 6, 2, 3]))

Key takeaways

• Sentinel zero forces the stack to empty at the end.
• Width uses previous smaller index boundary.
• Same pattern powers many “nearest smaller on both sides” problems.