 All Problems
Online Stock Span
medium
stack
design
monotonic stack
amazon
microsoft
google

Design an algorithm that collects daily price quotes for a stock and returns the span of that stock's price for the current day. The span 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.

Example:

Input:
next 100
next 80
next 60
next 70
next 60
next 75
next 85

Output:
1
1
1
2
1
4
6

Constraints:

  • 1 ≤ price ≤ 10⁵
  • At most 10⁴ calls to next.

Input format: One command per line: "next PRICE".

Output format: Print the span for each call.

Run to check your code against the sample cases, or submit to run every case