How far back is it the best?
prices[d] is a share's price on day d. The span of a day is how many days in a row, ending with that day and going back, had a price no higher than that day's price. A day always counts itself.
Return the span of every day, in order.
- Input
prices = [30,25,27,27,40,10]- Output
[1,1,2,3,5,1]
The second 27 looks back over 27 and 25 before 30 stops it; 40 is higher than everything before it.
- Input
prices = [5,5,5]- Output
[1,2,3]
An equal price does not stop the count.
Limits
1 <= prices.length <= 1000001 <= prices[d] <= 100000
Hints
Hint 1
Keep a stack of days whose price is still the highest seen since them.
Hint 2
Pop every day that is no higher than today: today now covers them.
Where this was reported
- Flipkart, SDE-1 interview (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.