Daily price span with a monotonic stack
The "span" of a price on a given day is the number of consecutive days ending today on which the price was less than or equal to today's price. It is a simple momentum gauge computed as the ticks stream in.
prices = [100, 80, 60, 70, 60, 75, 85]
-> [1, 1, 1, 2, 1, 4, 6]
Return the span for every day in O(n) total time. A per-day backward scan is O(n^2).
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.