Medium

Online Stock Span

088

Given daily prices, return the stock span for each day.

EXAMPLES

Example 1

Input
{
  "prices": [
    100,
    80,
    60,
    70,
    60,
    75,
    85
  ]
}

Output
[
  1,
  1,
  1,
  2,
  1,
  4,
  6
]

FUNCTION SHAPE

prices: intArray→intArray

SOLUTION NOTE

Dynamic NGE template. Store (price, span_value) pairs to save redundant work.

Reveal reference solution +

pythonREFERENCE

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

    def next(self, price: int) -> int:
        ans = 1
        while self.stack and self.stack[-1][0] <= price:
            ans += self.stack.pop()[1]
        self.stack.append((price, ans))
        return ans

TimeO(n) amortized

SpaceO(n)

Open on LeetCode ↗