Identify next-greater problems
Updated
Signals: next larger to the right, days until warmer, nearest smaller left, histogram rectangles, stock span. Recipe: monotonic stack, pop-while, write on pop, sentinel leftovers. Not largest in the whole array (that's a scan or heap).
What to focus on
If the candidate must be nearest in index among those that beat the value, a monotonic stack is the usual linear tool. If any larger anywhere, a running max from the right is enough and simpler.
Worked examples
nearest right
a = [2, 1, 3]- next greater
Result: monotonic stack
global max
a = [2, 1, 3]- max is 3 for everyone needing 'any greater'
Result: one scan, not a stack
span
a = [2, 1, 2, 4]- how far left until a greater
- previous greater
Result: stack of indices
Try it
Write classifyNext(kind). kind is "nearestRight", "globalMax", or "span". Return "stack" or "scan". Nearest vs any is the fork. a = [2, 1, 3] → monotonic stack. a = [2, 1, 3] → one scan, not a stack. a = [2, 1, 2, 4] → stack of indices.
a is a non-empty list of integers. Classify nearest vs any.