Online stock span
Write a class StockSpanner that receives a stock's closing price one day at a time. Each call next(price) records today's price and returns today's span: the number of consecutive days, ending with today and counting today, on which the price was at or below today's price.
For example, if the earlier prices were 7, 2, 5, 4 and today's price is 6, then going back from today the days at 6, 4, 5 and 2 are all at or below 6, and the 7 stops the run. The span is 4.
Each StockSpanner keeps its own history of prices, and each call should stay fast even after many days.
StockSpanner(), then next(30), next(25), next(28), next(35), next(20)Output1, 1, 2, 4, 1One span per call. The 28 covers itself and the 25 before it, and the 30 stops it. The 35 covers all four days so far. The 20 is below the 35, so it covers only itself.
StockSpanner(), then next(10), next(10), next(10)Output1, 2, 3An equal price counts: each day covers itself and every earlier 10.
1 ≤ price ≤ 105
At most 105 calls to
next.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.