How do I calculate the stock span using a stack?

By maintaining a stack in monotonic decreasing order, you can calculate the span of a stock price by comparing it to the prices at the indices in the stack. The span for the current price is the difference between the current index and the index of the last price that was greater than or equal to it.

What is the time complexity of the solution?

The average time complexity is O(1) per operation due to the stack's efficient management. In the worst case, the time complexity can be O(n) if all prices are strictly increasing.

What does monotonic stack mean in the context of this problem?

A monotonic stack ensures that the prices in the stack are in a decreasing order. This property allows efficient span calculation by removing redundant comparisons for previously processed prices.

What other data structures could be used for the Online Stock Span problem?

While a stack is the most efficient data structure for this problem, alternatives such as arrays or queues could be used, but they would not offer the same performance, especially for larger inputs.

How does GhostInterview help with this problem?

GhostInterview provides guided solutions and practice problems that focus on stack-based state management, helping you master the techniques necessary for efficient problem-solving in coding interviews.

#901

Medium

auto_awesome栈·状态

LeetCode 题解工作台

股票价格跨度

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度。当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85] ，那么股票跨度将是 [1,1,1,2,1,…

栈设计单调栈数据流

题目描述

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度。

当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

StockSpanner() 初始化类对象。
int next(int price) 给出今天的股价 price ，返回该股票当日价格的跨度。

示例：

输入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]

解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80);  // 返回 1
stockSpanner.next(60);  // 返回 1
stockSpanner.next(70);  // 返回 2
stockSpanner.next(60);  // 返回 1
stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85);  // 返回 6

提示：

1 <= price <= 10⁵
最多调用 next 方法 10⁴ 次

lightbulb

解题思路

方法一：单调栈

根据题目描述，我们可以知道，对于当日价格 $price$ ，从这个价格开始往前找，找到第一个比这个价格大的价格，这两个价格的下标差 $cnt$ 就是当日价格的跨度。

这实际上是经典的单调栈模型，找出左侧第一个比当前元素大的元素。

我们维护一个从栈底到栈顶价格单调递减的栈，栈中每个元素存放的是 $(price, cnt)$ 数据对，其中 $price$ 表示价格，而 $cnt$ 表示当前价格的跨度。

出现价格 $price$ 时，我们将其与栈顶元素进行比较，如果栈顶元素的价格小于等于 $price$ ，则将当日价格的跨度 $cnt$ 加上栈顶元素的跨度，然后将栈顶元素出栈，直到栈顶元素的价格大于 $price$ ，或者栈为空为止。

最后将 $(price, cnt)$ 入栈，返回 $cnt$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是调用 next(price) 的次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

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


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands the importance of using a stack for efficient state management.
question_mark
Candidate demonstrates the ability to optimize a brute-force solution to O(1) complexity.
question_mark
Candidate is able to articulate the trade-offs between time complexity and space complexity in stack-based problems.

warning

常见陷阱

外企场景

error
Not maintaining the stack in monotonic order, which can lead to incorrect span calculations.
error
Failing to efficiently handle the worst-case scenario where all stock prices are in increasing order.
error
Not fully utilizing the stack’s properties, such as avoiding redundant calculations for previously processed prices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing a solution with an alternative data structure (e.g., queue or array) for span calculation.
arrow_right_alt
Handling the problem with multiple stock spans, each with separate stock price inputs.
arrow_right_alt
Optimizing for a stream of data with real-time updates and dynamic span calculations.

help

常见问题

外企场景

继续练习

#1472 设计浏览器历史记录 #895 最大频率栈 #907 子数组的最小值之和