450. Price Span
A trader watches a share price once per day and wants a quick measure of how strong each day is. For a given day, the span is the number of consecutive days, counting backwards from that day and including it, on which the price was less than or equal to that day's price.
Implement the class PriceSpan with a constructor that takes no arguments and the method next(price). Each call announces the price of the next day in the stream and returns the span of that day. The walk back stops at the first earlier day whose price is strictly greater than today's price, or at the first day ever recorded. Prices arrive one at a time and the whole history must not be rescanned on every call.
Example 1
- Input:
- operations = ["PriceSpan","next","next","next","next","next","next","next"]arguments = [[],[73],[74],[72],[72],[75],[70],[71]]
- Output:
- [null,1,2,1,2,5,1,2]
- Explanation:
Spans: 73 has 1; 74 covers 73 and itself, so 2; 72 only itself, 1; the second 72 includes the first 72, so 2; 75 beats everything before it, 5; 70 has 1; 71 covers 70 and itself, 2.
Example 2
- Input:
- operations = ["PriceSpan","next","next","next","next","next"]arguments = [[],[9],[8],[8],[9],[7]]
- Output:
- [null,1,1,2,4,1]
- Explanation:
Spans: 1; 1 (8 is below 9 so it stops); 2 (the earlier equal 8 counts); 4 (8, 8 and itself are all at most 9, and 9 is equal); 1.
Constraints
1 ≤ price ≤ 105
At most 104 calls to next.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) amortized per call
- Space
- O(n)