BL
U

89. Online Stock Span

Med.

Problem Description

Given daily stock prices for NN days, calculate the stock span for each day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today's price.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers representing stock prices.

Output Format

Print NN space-separated integers representing the span for each day.

Example 1:
Input:
7
100 80 60 70 60 75 85
Output:
1 1 1 2 1 4 6
Explanation: Spans calculated looking backward.
Example 2:
Input:
4
10 20 30 40
Output:
1 2 3 4
Explanation: Strictly increasing prices give increasing spans.
Example 3:
Input:
4
40 30 20 10
Output:
1 1 1 1
Explanation: Strictly decreasing prices all have span 1.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online