Online Stock Span
Recognize the pattern
Brute force idea
The naive version of Online Stock Span sounds like this: For each day, scan backward counting — total. Re-scans overlapping portions. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
Better approach
The real unlock in Online Stock Span comes when you notice this: Monotonic decreasing stack of (price, span) pairs. When today's price ≥ stack top, pop and absorb that span. The accumulated span is pushed with today's price. amortized. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Key invariant
The compass for Online Stock Span is this: The stack holds prices in decreasing order. When a new price dominates stack entries, their spans are absorbed — they'll never be relevant again because today's price overshadows them. As long as that statement keeps holding, you can trust the steps built on top of it.
Watch out for
One easy way to drift off course in Online Stock Span is this: Not accumulating spans when popping — each popped entry's span must be added to the current day's span, because those days are now covered by today. The fix is usually to return to the meaning of each move, not just the steps themselves.