Algorithms / Monotonic Stack Next Greater
Least You Need to Know: Monotonic Stacks and Next-Greater Patterns
A monotonic stack keeps elements in sorted stack order so that a new value can resolve many waiting positions at once. This turns repeated scanning into a single left-to-right pass for next-greater and waiting-time style problems.
جو کم از کم جاننا ضروری ہے
- For next-greater problems, the stack usually stores indices whose answer has not been found yet.
- A new larger value can pop smaller waiting values and become their answer.
- The chosen monotone direction depends on whether you need next greater, next smaller, previous greater, or previous smaller.
- Indices are often more useful than raw values because you may need distances or window membership.
- Each index is pushed once and popped once, giving linear-time behavior.
اہم علامتیں
stack
LIFO structure holding unresolved candidates
monotone decreasing
stored values decrease from bottom to top
next greater
first later value strictly larger than the current one
مختصر حل شدہ مثال
- Scan array values from left to right.
- Keep a decreasing stack of indices whose next greater value has not appeared yet.
- When a larger value arrives, pop all smaller indices and record the new value or new index as their answer.
- Then push the current index.
عام غلطیاں
- Students often store values when later they need distances between indices.
- Students often forget that equal values require a deliberate tie rule.
- Students often think monotonic stacks sort the entire array instead of solving pending boundary questions.
اس قسم کے سوال کو کیسے پہچانیں
- The prompt asks for next greater, warmer day, first taller bar, or nearest later blocker.
- Each position waits for the first later element meeting a comparison.
- A brute-force nested scan would repeatedly revisit the same comparisons.
Next recommended lesson
Continue through this topic with Least You Need to Know: Offline Sorting, Event Sweeps, and Ordered Processing.
Least You Need to Know: Offline Sorting, Event Sweeps, and Ordered ProcessingRelated lessons
Keep going with nearby lessons in the same topic.