Skip to content

901. Online Stock Span 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class StockSpanner {
 public:
  int next(int price) {
    int span = 1;
    while (!stack.empty() && stack.top().first <= price)
      span += stack.top().second, stack.pop();
    stack.emplace(price, span);
    return span;
  }

 private:
  stack<pair<int, int>> stack;  // (price, span)
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class StockSpanner {
  public int next(int price) {
    int span = 1;
    while (!stack.isEmpty() && stack.peek().getKey() <= price)
      span += stack.pop().getValue();
    stack.push(new Pair<>(price, span));
    return span;
  }

  // (price, span)
  private Stack<Pair<Integer, Integer>> stack = new Stack<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class StockSpanner:
  def __init__(self):
    self.stack = []  # (price, span)

  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