Online Stock Span

901. 股票价格跨度

分析

维护单调递减栈：
- 栈中存储之前的股票价格以及对应的日期索引
- 保证栈中从栈底到栈顶的股票价格递减。这样可以快速找到比当前价格大的最近日期
核心操作：
- 对于当前股价 price：
  - 不断弹出栈顶元素，直到栈顶价格大于当前价格
  - 此时栈顶对应的索引即为最近一个比当前价格高的日期
- 当前跨度为：当前日期索引减去栈顶索引
边界处理：
- 初始化时，将一个虚拟价格（如 10^6 ）和一个虚拟日期（如 -1）入栈，方便处理第一天的数据

时间复杂度

每个价格最多会被栈操作一次（入栈和出栈各一次），因此所有操作的总时间复杂度为 O(n) ，每次调用 next 的均摊时间复杂度为 O(1)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class StockSpanner
{
public:
    std::stack<int> prices; // 单调栈存储股票价格
    std::stack<int> day;    // 单调栈存储对应的日期索引
    int cur = 0;            // 当前的日期索引

    StockSpanner()
    {
        // 初始化栈：存入虚拟的最大价格和虚拟日期
        prices.push(1e6);
        day.push(-1);
    }

    int next(int price)
    {
        // 弹出所有小于等于当前价格的栈顶元素
        while (prices.top() <= price)
        {
            prices.pop();
            day.pop();
        }

        // 计算跨度：当前日期索引减去栈顶索引
        int res = cur - day.top();

        // 将当前价格和索引入栈
        prices.push(price);
        day.push(cur++);

        return res;
    }
};