LC 901. Online Stock Span

The problem

Solution - $O(n)$ Time

My initial thought was to use an array to store the prices and check through them every time a price is added for the span. This would've been an $O(n^2)$ approach, but the topic that led me to this problem was monotonic stacks. Based on the premise, the setup for the monotonic stack made sense to me, that I would need to implement it as strictly decreasing, but I was stumped about storing the spans and needed to get a tip from the discussions. The part that I was confused about was that by storing the span of a price in the stack, popped values no longer need to be kept track of because they're added to the span of the next price being pushed.

In the end, I was disappointed I needed a tip on this because I felt that I was quite close to getting a solution. Either way, I've learned the pattern and will keep reviewing and progressing so that when I see it again, I'll be able to solve it 💪!

class StockSpanner {
  stack: number[][]
  constructor() {
    this.stack = []
  }

  next(price: number): number {
    let span = 1
    while (this.stack.length && this.top()[0] <= price) {
      span += this.stack.pop()[1]
    }
    this.stack.push([price, span])
    return span
  }

  top(): number[] {
    return this.stack[this.stack.length - 1]
  }
}