Practice/Meta/Leetcode 901. Online Stock Span

Leetcode 901. Online Stock Span

CodingOptional

Problem

Design a data structure that processes a stream of product prices in real-time. For each incoming price, you need to calculate how many consecutive recent prices (including the current one) were less than or equal to this price.

You'll implement a class StreamAnalyzer with the following methods:

• Constructor: Initializes the analyzer with no historical data
• record_price(price): Accepts a new price and returns the span value

The span is defined as the maximum number of consecutive days ending with today where each day's price was less than or equal to today's price.

Requirements

1. Implement the StreamAnalyzer class with an __init__ method and a record_price method
2. The record_price method must return an integer representing the span
3. Prices are processed in chronological order (you cannot look ahead)
4. Your solution should handle multiple price recordings efficiently

Constraints

• 1 ≤ number of calls to record_price ≤ 10,000
• 1 ≤ price ≤ 100,000
• All prices are positive integers
• Target time complexity: O(1) amortized per record_price call
• Target space complexity: O(n) where n is the number of prices recorded

Examples

Example 1:

analyzer = StreamAnalyzer() analyzer.record_price(100) # Returns 1 analyzer.record_price(80) # Returns 1 analyzer.record_price(60) # Returns 1 analyzer.record_price(70) # Returns 2 (days with prices [60, 70] are ≤ 70) analyzer.record_price(60) # Returns 1 analyzer.record_price(75) # Returns 4 (days with prices [60, 70, 60, 75] are ≤ 75) analyzer.record_price(85) # Returns 6 (days with prices [80, 60, 70, 60, 75, 85] are ≤ 85)

Example 2:

analyzer = StreamAnalyzer() analyzer.record_price(10) # Returns 1 analyzer.record_price(20) # Returns 2 analyzer.record_price(30) # Returns 3

Example 3:

analyzer = StreamAnalyzer() analyzer.record_price(50) # Returns 1 analyzer.record_price(40) # Returns 1 analyzer.record_price(30) # Returns 1