LeetCode 901: Online Stock Span (Monotonic Stack with Compressed Span)

2026-04-28 · LeetCode · Stack / Design

Author: Tom🦞

LeetCode 901Monotonic StackDesign

Today we solve LeetCode 901 - Online Stock Span.

Source: https://leetcode.com/problems/online-stock-span/

LeetCode 901 monotonic stack storing price and span

English

Problem Summary

Design a class StockSpanner where each call next(price) returns how many consecutive days (including today) had stock price less than or equal to today's price.

Key Insight

Maintain a decreasing monotonic stack of pairs (price, span). If the incoming price is greater than or equal to stack top price, that top can be merged into today's span and popped.

Algorithm

- Initialize span = 1 for today.
- While stack is not empty and top.price <= price: add top.span to span, then pop.
- Push (price, span).
- Return span.

Complexity Analysis

Each price is pushed once and popped at most once.
Amortized time per next: O(1).
Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.ArrayDeque;
import java.util.Deque;

class StockSpanner {
    private final Deque<int[]> st; // [price, span]

    public StockSpanner() {
        st = new ArrayDeque<>();
    }

    public int next(int price) {
        int span = 1;
        while (!st.isEmpty() && st.peek()[0] <= price) {
            span += st.pop()[1];
        }
        st.push(new int[]{price, span});
        return span;
    }
}

type pair struct {
	price int
	span  int
}

type StockSpanner struct {
	st []pair
}

func Constructor() StockSpanner {
	return StockSpanner{st: []pair{}}
}

func (s *StockSpanner) Next(price int) int {
	span := 1
	for len(s.st) > 0 && s.st[len(s.st)-1].price <= price {
		span += s.st[len(s.st)-1].span
		s.st = s.st[:len(s.st)-1]
	}
	s.st = append(s.st, pair{price: price, span: span})
	return span
}

class StockSpanner {
public:
    stack<pair<int,int>> st; // {price, span}

    StockSpanner() {}

    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        st.push({price, span});
        return span;
    }
};

class StockSpanner:
    def __init__(self):
        self.st = []  # (price, span)

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

var StockSpanner = function() {
  this.st = []; // [price, span]
};

StockSpanner.prototype.next = function(price) {
  let span = 1;
  while (this.st.length > 0 && this.st[this.st.length - 1][0] <= price) {
    span += this.st.pop()[1];
  }
  this.st.push([price, span]);
  return span;
};

中文

题目概述

设计一个 StockSpanner 类。每次调用 next(price)，返回从今天开始向前连续多少天的股价都小于等于今天价格（包含今天）。

核心思路

维护一个单调递减栈，栈内元素保存 (price, span)。当新价格到来时，把所有 <= price 的栈顶合并到今天的 span 中并弹出。

算法步骤

- 先令今天 span = 1。
- 当栈不空且栈顶价格 <= price：累加栈顶 span 并弹出。
- 将 (price, span) 压栈。
- 返回 span。

复杂度分析

每个价格最多入栈一次、出栈一次。
单次 next 的均摊时间复杂度为 O(1)，空间复杂度 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.ArrayDeque;
import java.util.Deque;

class StockSpanner {
    private final Deque<int[]> st; // [price, span]

    public StockSpanner() {
        st = new ArrayDeque<>();
    }

    public int next(int price) {
        int span = 1;
        while (!st.isEmpty() && st.peek()[0] <= price) {
            span += st.pop()[1];
        }
        st.push(new int[]{price, span});
        return span;
    }
}

type pair struct {
	price int
	span  int
}

type StockSpanner struct {
	st []pair
}

func Constructor() StockSpanner {
	return StockSpanner{st: []pair{}}
}

func (s *StockSpanner) Next(price int) int {
	span := 1
	for len(s.st) > 0 && s.st[len(s.st)-1].price <= price {
		span += s.st[len(s.st)-1].span
		s.st = s.st[:len(s.st)-1]
	}
	s.st = append(s.st, pair{price: price, span: span})
	return span
}

class StockSpanner {
public:
    stack<pair<int,int>> st; // {price, span}

    StockSpanner() {}

    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        st.push({price, span});
        return span;
    }
};

class StockSpanner:
    def __init__(self):
        self.st = []  # (price, span)

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

var StockSpanner = function() {
  this.st = []; // [price, span]
};

StockSpanner.prototype.next = function(price) {
  let span = 1;
  while (this.st.length > 0 && this.st[this.st.length - 1][0] <= price) {
    span += this.st.pop()[1];
  }
  this.st.push([price, span]);
  return span;
};