Loading problem...
Design a data structure that processes a continuous stream of price values and computes the dominance span for each incoming price in real-time.
The dominance span of a price on a given day is defined as the maximum count of consecutive days (including the current day and extending backward in time) during which all observed prices were less than or equal to the current day's price.
Consider the following illustrative examples:
[7, 2, 1, 2] and today's price is 2, the dominance span is 4 because the price has remained at or below 2 for all four consecutive days (going backward from today).[7, 34, 1, 2] and today's price is 8, the dominance span is 3 because going backward from today, only the last three prices (1, 2, and 8 itself) satisfy the condition of being at or below 8.Your Task:
Implement the PriceDominanceTracker class with the following interface:
PriceDominanceTracker(): Initializes a new instance of the tracker with an empty price history.int recordPrice(int price): Records a new price entry in the stream and returns the dominance span for this price based on all previously recorded prices.The solution must efficiently handle a high volume of price recordings while maintaining optimal query performance for each new entry.
operations = ["PriceDominanceTracker", "recordPrice", "recordPrice", "recordPrice", "recordPrice", "recordPrice", "recordPrice", "recordPrice"]
arguments = [[], [100], [80], [60], [70], [60], [75], [85]][null, 1, 1, 1, 2, 1, 4, 6]PriceDominanceTracker tracker = new PriceDominanceTracker(); tracker.recordPrice(100); // returns 1 (only today's price) tracker.recordPrice(80); // returns 1 (80 < 100, so dominance breaks at day 1) tracker.recordPrice(60); // returns 1 (60 < 80, so dominance breaks at day 1) tracker.recordPrice(70); // returns 2 (70 >= 60, so we count 2 consecutive days) tracker.recordPrice(60); // returns 1 (60 < 70, so dominance breaks at day 1) tracker.recordPrice(75); // returns 4 (75 >= 60 >= 60 >= 70 dominates 4 consecutive days) tracker.recordPrice(85); // returns 6 (85 dominates all prices back to 80, spanning 6 days)
operations = ["PriceDominanceTracker", "recordPrice", "recordPrice", "recordPrice", "recordPrice", "recordPrice"]
arguments = [[], [10], [20], [30], [40], [50]][null, 1, 2, 3, 4, 5]With strictly increasing prices, each new price dominates all previous prices. The dominance span grows linearly: 1, 2, 3, 4, 5 for the five price recordings.
operations = ["PriceDominanceTracker", "recordPrice", "recordPrice", "recordPrice", "recordPrice", "recordPrice"]
arguments = [[], [50], [40], [30], [20], [10]][null, 1, 1, 1, 1, 1]With strictly decreasing prices, each new price is immediately blocked by the previous higher price. Every dominance span is exactly 1, representing only the current day.
Constraints