Monotonic stack — order பேணுதல்

Monotonic stack — values/indexes order; ஒவ்வொன்றும் ஒருமுறை enter/leave amortized.

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 0 — முடிவில் flush.
• Width — prev smaller boundary.
• இரு பக்க nearest smaller.