Online Stock Span

For each new price, count the run of days up to today with a price no higher than today's. A stack of (price, span) pairs lets each call skip whole runs at once.

The idea

An entry (price, span) on the stack stands for a run of span days that all had a price no higher than price. When today's price is at least as high as the top entry, today beats that whole run, so pop the entry and add its span to today's. Stop at the first higher price: it blocks the run. Push today as one entry covering everything it swallowed, so later days can skip all of it in one step.

Code

public class StockSpanner {
    // (price, span) pairs; prices strictly fall from bottom to top
    private readonly Stack<(int price, int span)> stack = new();

    public int Next(int price) {
        int span = 1; // today counts itself
        while (stack.Count > 0 && stack.Peek().price <= price)
            span += stack.Pop().span; // take over the days that entry covered
        stack.Push((price, span));
        return span;
    }
}

Tips

• Use <= in the loop: a day with the same price still counts toward the span.
• Every price is pushed once and popped at most once, so n calls cost O(n) in total even though one call can pop many entries.
• The prices left on the stack strictly fall from bottom to top. Each one is still higher than everything after it, so a future day may stop on it.

In the .NET library

Stack<(int price, int span)> stores a named value tuple, so stack.Peek().price reads clearly and no extra class is needed.