Stock Span
mediumPlacement Coding+20 XPTime limit 2s
For each day, the span of the share price is the number of consecutive days, ending today and going backwards, on which the price was less than or equal to today's price (today counts). For prices 100 80 60 70 60 75 85 the spans are 1 1 1 2 1 4 6.
Input:
- line 1:
n - line 2: the
ndaily prices
Output: the n spans, separated by spaces.
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ price ≤ 10⁹.
Think about it: keep a stack of indexes of days with higher prices. For a new day, pop every day whose price is ≤ today's; the index left on top is the previous higher day, and the span is the distance to it. Each day is pushed and popped once — O(n).
Sample input 1
7 100 80 60 70 60 75 85
Sample output 1
1 1 1 2 1 4 6
Sample input 2
3 10 10 10
Sample output 2
1 2 3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).