Monotonic Stack
Keep unresolved indexes in stack order so a new greater value can answer old questions immediately.
0 of 3 problems solved
Monotonic Stack
Keep unresolved indexes in stack order so a new greater value can answer old questions immediately.
- •Am I waiting for the next greater value?
- •Should the stack store indexes so I can compute distance?
- •Do smaller temperatures get resolved when a warmer day appears?
Daily Temperatures is a waiting-room problem. Each day is asking, 'How long until someone warmer shows up?' A monotonic stack keeps days that are still waiting for better weather. When a hotter day arrives, it immediately answers old questions and kicks those colder days out of the stack.
The stack holds unresolved days, not the final answers.
- 1Store indexes in the stack so you can calculate day differences later.
- 2Move through temperatures from left to right.
- 3While the current day is warmer than the day on top of the stack, pop that older index and fill its answer.
- 4Push the current index when it is still waiting for a warmer day.
Storing temperatures instead of indexes makes it impossible to compute how many days someone waited.
Baseball Game
Simulate with a stack. '+' sums the top two, 'D' doubles the top, 'C' removes the top. Process each operation in order.
Maximal Rectangle
Treat each row as a base for a histogram using accumulated heights. Run Largest Rectangle in Histogram on each row's heights.