# LeetCode 901: Online Stock Span

## Problem Restatement

We need to design a class called `StockSpanner`.

The class receives stock prices one day at a time through the method `next(price)`.

For each new price, we return its stock span.

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

For example:

```python
prices = [100, 80, 60, 70, 60, 75, 85]
```

The spans are:

```python
[1, 1, 1, 2, 1, 4, 6]
```

For price `75`, the span is `4` because the last four prices are:

```python
[60, 70, 60, 75]
```

All of them are less than or equal to `75`.

## Input and Output

| Item | Meaning |
|---|---|
| Class | `StockSpanner` |
| Method | `next(price)` |
| Input | Today's stock price |
| Output | Span of today's stock price |
| Stream behavior | Prices arrive one at a time |
| Comparison rule | Previous prices must be `<=` today's price |

The class shape is:

```python
class StockSpanner:

    def __init__(self):
        ...

    def next(self, price: int) -> int:
        ...
```

## Examples

Input:

```python
stockSpanner = StockSpanner()
stockSpanner.next(100)
stockSpanner.next(80)
stockSpanner.next(60)
stockSpanner.next(70)
stockSpanner.next(60)
stockSpanner.next(75)
stockSpanner.next(85)
```

Output:

```python
1
1
1
2
1
4
6
```

Step by step:

| Day | Price | Span | Reason |
|---:|---:|---:|---|
| 1 | 100 | 1 | Only today counts |
| 2 | 80 | 1 | Previous price `100` is greater |
| 3 | 60 | 1 | Previous price `80` is greater |
| 4 | 70 | 2 | `60 <= 70`, but `80 > 70` |
| 5 | 60 | 1 | Previous price `70` is greater |
| 6 | 75 | 4 | `60, 70, 60, 75` are all `<= 75` |
| 7 | 85 | 6 | `80, 60, 70, 60, 75, 85` are all `<= 85`, but `100 > 85` |

## First Thought: Brute Force

A direct method is to store every price seen so far.

For each new price, walk backward through the list and count how many consecutive prices are less than or equal to the current price.

```python
class StockSpanner:

    def __init__(self):
        self.prices = []

    def next(self, price: int) -> int:
        self.prices.append(price)

        span = 0
        i = len(self.prices) - 1

        while i >= 0 and self.prices[i] <= price:
            span += 1
            i -= 1

        return span
```

This is correct, but it can be slow.

## Problem With Brute Force

If prices keep increasing, each new call may scan all previous prices.

Example:

```python
[10, 20, 30, 40, 50]
```

For `50`, the method scans all five prices.

For many calls, the total cost can become quadratic.

| Metric | Value |
|---|---|
| Time per `next` | `O(n)` |
| Total time for `n` calls | `O(n^2)` |
| Space | `O(n)` |

We need to avoid rechecking prices that have already been absorbed into earlier spans.

## Key Insight

When a previous price is less than or equal to today's price, it belongs to today's span.

If that previous price already had a span, then all prices inside that previous span also belong to today's span.

So instead of storing only prices, store pairs:

```python
(price, span)
```

The stack keeps prices in strictly decreasing order from bottom to top.

When a new price arrives, we pop every previous price that is less than or equal to it. Each popped item contributes its whole span.

This is the main compression.

For example, after processing:

```python
[100, 80, 60, 70]
```

The stack is:

```python
[(100, 1), (80, 1), (70, 2)]
```

The price `60` before `70` no longer needs its own stack entry because it has been included in the span of `70`.

## Algorithm

Maintain a stack of pairs:

```python
(price, span)
```

For each `next(price)` call:

1. Start with `span = 1` for today.
2. While the stack is not empty and the top price is less than or equal to `price`, pop it.
3. Add the popped span to the current span.
4. Push `(price, span)` onto the stack.
5. Return `span`.

The stack only keeps prices that can stop a future span.

A smaller or equal price below today's price cannot stop any future span because today's price is newer and at least as large.

## Correctness

The stack stores groups of consecutive days.

Each pair `(p, s)` means there is a block of `s` consecutive days ending at price `p`, and every price in that block is less than or equal to `p`.

The stack is kept in decreasing price order.

When `next(price)` is called, every stack item with `p <= price` belongs to today's span. Since its whole block also has prices less than or equal to `p`, every price in that block is also less than or equal to today's `price`.

So we can safely add the whole stored span at once.

The popping stops when the stack is empty or the top price is greater than today's price.

If the stack is empty, all previous grouped prices are less than or equal to today's price, so the span includes all previous days plus today.

If the top price is greater, it is the nearest previous price that blocks the span. Any price before it cannot be included because the span must be consecutive.

Therefore, the algorithm returns exactly the number of consecutive days ending today whose prices are less than or equal to today's price.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time per `next` | `O(1)` amortized | Each price is pushed once and popped at most once |
| Space | `O(n)` | In the worst case, prices are strictly decreasing and all remain in the stack |

A single call can pop many elements, but across all calls, each element can be removed only once.

## Implementation

```python
class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]

        self.stack.append((price, span))

        return span
```

## Code Explanation

The stack stores compressed history:

```python
self.stack = []
```

Each entry is:

```python
(price, span)
```

For every new price, we count today first:

```python
span = 1
```

Then we remove all previous prices that today's price dominates:

```python
while self.stack and self.stack[-1][0] <= price:
    span += self.stack.pop()[1]
```

The important part is adding the popped span, not just `1`.

A popped entry may represent many previous days.

After all smaller or equal prices are absorbed, we store today's compressed result:

```python
self.stack.append((price, span))
```

Then we return the answer:

```python
return span
```

## Testing

```python
def run_tests():
    s = StockSpanner()

    assert s.next(100) == 1
    assert s.next(80) == 1
    assert s.next(60) == 1
    assert s.next(70) == 2
    assert s.next(60) == 1
    assert s.next(75) == 4
    assert s.next(85) == 6

    s = StockSpanner()
    assert [s.next(x) for x in [10, 20, 30, 40]] == [1, 2, 3, 4]

    s = StockSpanner()
    assert [s.next(x) for x in [40, 30, 20, 10]] == [1, 1, 1, 1]

    s = StockSpanner()
    assert [s.next(x) for x in [50, 50, 50]] == [1, 2, 3]

    s = StockSpanner()
    assert [s.next(x) for x in [31, 41, 48, 59, 79]] == [1, 2, 3, 4, 5]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[100, 80, 60, 70, 60, 75, 85]` | Matches the sample behavior |
| Increasing prices | Every new price absorbs all previous prices |
| Decreasing prices | Every span stays `1` |
| Equal prices | Confirms the `<=` rule |
| All increasing mixed values | Checks repeated popping and span accumulation |