Monotonic Stack & Queue
Keep a stack or deque in sorted order to answer "next greater", "largest rectangle", and sliding-window max in O(n).
This topic is part of Pro.
Free covers the C and Python courses, the first three DSA topics, the opening system design lessons and the beginner AI lessons, all with the full coach. Pro opens the rest of the library in the FollowtheDamnCode app.
What is in it
- 1Next greater elementKeep a decreasing stack of items still waiting; each new item answers everyone smaller than it. Pro
- 2Largest rectangle in a histogramEach bar's best rectangle stretches until the first shorter bar on either side — a monotonic stack finds both. Pro
- 3Sliding window maximum (monotonic deque)Keep a deque of window indices with decreasing values; the front is always the window's maximum. Pro