Stacks and Monotonic Structures
Retrieval: when is it a stack?
Two problems rebuilt cold, plus the signal that separates a stack problem from a window problem.
Key idea
Three signals
Nesting means a plain stack. Something opens, something else opens inside it, and the inner one must close first.
A question about the nearest position in some direction with a particular relationship means a monotonic stack. The words nearest, next, previous, first, and until are the giveaway.
A question about a contiguous range whose contents can be summarized means a window. If the summary is an extreme value rather than a sum or a count, the window needs a monotonic deque, which is both patterns at once.
Gotcha
The pattern is not the data type
Both a window and a monotonic stack use a list of indexes and a while loop, so the code looks similar and the reasoning is different. A window's left edge moves because the window became illegal. A monotonic stack pops because a candidate became useless forever.
If you can say which of those two sentences describes your loop, you have understood it. If you cannot, you are pattern matching on syntax.
Which structure does this want?
For each building in a row, report how many buildings to its right are visible before a taller one blocks the view. Which approach fits?
Daily Temperatures, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Trapping Rain Water, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.