Stock Span Problem — All Three Variants

Problem Statement

Given an array of daily stock prices, solve the following three variants:

Variant 1: Basic Stock Span

For each day i, find the span — the number of consecutive days just before day i (including day i itself) where the price was less than or equal to price[i].

Variant 2: Circular Next Greater Element

Find the next greater element for each stock price, but the array is circular (the last element wraps around to the first).

Variant 3: Online Stock Span

Design a class that receives stock prices one at a time via next(price) and returns the span for each new price in O(1) amortized time. You cannot store all prices and recompute each time.

Constraints

• 1 <= prices.length <= 10^5
• 1 <= prices[i] <= 10^5
• For Variant 3: at most 10^5 calls to next()

Example

Variant 1:

Input:  [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]

Variant 2:

Input:  [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, 4]
// 3's next greater is 4 (wraps around)

Variant 3:

next(100) → 1
next(80)  → 1
next(60)  → 1
next(70)  → 2
next(60)  → 1
next(75)  → 4
next(85)  → 6

Follow-ups

1. What data structure makes all three variants O(n) or O(1) amortized?
2. For Variant 2, how do you handle the circular traversal without duplicating the array?
3. For Variant 3, what's the worst-case space complexity? Can you bound it?
4. How would you extend Variant 3 to also support getMax(k) — max price in last k days?