A trading dashboard receives one closing price per day and shows how strong today's price is. The streak for a day is the number of consecutive days, ending with today and counting backwards, on which the price was less than or equal to today's price. Today always counts, so a streak is at least 1.
Write a class StreakTracker:
StreakTracker()starts with no history.record(price)adds today's price and returns today's streak.
t = StreakTracker()
t.record(30) # 1
t.record(25) # 1 (30 > 25 stops it)
t.record(28) # 2 (28, 25)
t.record(26) # 1
t.record(29) # 4 (29, 26, 28, 25; then 30 > 29)
t.record(40) # 6 (every day so far)
t.record(12) # 1
Constraints: up to 2 * 10^5 calls to record; prices are integers in [1, 10^9].
Walking back through the history on every call is O(n) per call, O(n²) in total when prices keep rising. Aim for amortized O(1) per call.
Show hint
once a day is covered by a later day's streak, a future streak that reaches that later day reaches all the days it covers too. So a day that's been swallowed never needs to be looked at on its own again.