Skills101
← All coding problems

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 n daily 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).

Loading editor…

Log in to run and submit your code — it's free.