Backward Price Span for Each Trading Day

Implement stockSpan

Given a sequence of daily prices prices, find, for every day, how many consecutive days — counting today, and walking backward — the price has stayed at or below today's price before a strictly higher price finally breaks the streak. This is a "previous greater element" problem wearing a counting hat: instead of the value of the nearest strictly-higher day to the left, you want the distance to it. A monotonic decreasing stack of day indices tracks exactly that: whenever a new day's price is high enough to pop earlier days off (because it's at or above them), those days can never again bound anyone's span, since a higher wall now stands between them and the future. Once popping stops, whatever remains on top is the closest day still strictly higher — the boundary — and the span is simply the index gap to it (or all the way back to day 0, if the stack empties completely).

Example 1:

Input: prices = [45,30,35,40,25,50]

Output: [1,1,2,3,1,6]

Example 2:

Input: prices = [30,20,40,20,50,10,60]

Output: [1,1,3,1,5,1,7]

Example 3:

Input: prices = [10,10,10]

Output: [1,2,3]

+ 3 hidden test cases run on Submit.

Constraints:

  • 1 ≤ prices.length ≤ 15
  • 1 ≤ prices[i] ≤ 1000

prices =

[45, 30, 35, 40, 25, 50]