Medium

题目描述

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

股票价格在某一天的跨度是指从该天开始向前推（包括该天），连续多少天的股票价格小于或等于该天价格的最大天数。

例如，如果股票在过去四天的价格是 [7,2,1,2]，今天的价格是 2，那么今天的跨度是 4，因为从今天开始，连续 4 天的股票价格都小于或等于 2。

又例如，如果股票在过去四天的价格是 [7,34,1,2]，今天的价格是 8，那么今天的跨度是 3，因为从今天开始，连续 3 天的股票价格都小于或等于 8。

实现 StockSpanner 类：

  • StockSpanner() 初始化类的对象。
  • int next(int price) 返回给定今天价格 price 的股票价格跨度。

示例 1：

输入：
["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^5
  • 最多调用 next 方法 10^4 次

解题思路

解题思路

这是一个典型的单调栈问题。我们需要找到当前价格之前连续多少天的价格小于等于当前价格。

暴力解法： 每次调用 next 时，遍历之前所有的价格，计算连续天数。时间复杂度为 O(n)。

单调栈优化： 使用单调递减栈来优化查找过程。栈中存储 (价格, 跨度) 对：

  1. 当新价格到来时，如果栈顶元素的价格小于等于当前价格，说明这些天都包含在当前价格的跨度中
  2. 将栈顶元素弹出并累加其跨度，直到栈为空或栈顶价格大于当前价格
  3. 当前价格的跨度 = 1（自己） + 所有弹出元素的跨度之和
  4. 将当前价格和其跨度入栈

核心思想： 利用单调栈的性质，避免重复计算之前已经处理过的天数跨度。

例如序列 [100,80,60,70]：

  • 100: 栈空，跨度1，栈：[(100,1)]
  • 80: 80<100，跨度1，栈：[(100,1),(80,1)]
  • 60: 60<80，跨度1，栈：[(100,1),(80,1),(60,1)]
  • 70: 70>60，弹出(60,1)，跨度=1+1=2，栈：[(100,1),(80,1),(70,2)]

代码实现

class StockSpanner {
private:
    stack<pair<int, int>> st; // (price, span)
    
public:
    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.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

public class StockSpanner {
    private Stack<(int price, int span)> stack;

    public StockSpanner() {
        stack = new Stack<(int, int)>();
    }
    
    public int Next(int price) {
        int span = 1;
        
        while (stack.Count > 0 && stack.Peek().price <= price) {
            span += stack.Pop().span;
        }
        
        stack.Push((price, span));
        return span;
    }
}

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

StockSpanner.prototype.next = function(price) {
    let span = 1;
    
    while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
        span += this.stack.pop()[1];
    }
    
    this.stack.push([price, span]);
    return span;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(1)O(1)
next()均摊 O(1)O(n)

说明：

  • 时间复杂度：虽然单次调用可能是 O(n)，但每个元素最多入栈和出栈各一次，所以均摊时间复杂度是 O(1)
  • 空间复杂度：O(n)，其中 n 是调用次数，最坏情况下所有元素都在栈中

相关题目