The stock span problem
Asked at DRW, Jump Trading
The span of a stock on a given day is the number of consecutive days up to and including today on which the price was less than or equal to today's price.
prices = [100, 80, 60, 70, 60, 75, 85]
-> [1, 1, 1, 2, 1, 4, 6]
Return the span for every day in total.
Show a hint
When today's price is high, it swallows the spans of all the recent lower days at once. Keep a stack that remembers, for each surviving higher price, how many days it already accounts for.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.