0901. 股票价格跨度【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 单调栈

1. 📝 题目描述

• leetcode

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

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

• 例如，如果未来 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^5
• 最多调用 next 方法 10^4 次

2. 🎯 s.1 - 单调栈

c

typedef struct {
    int prices[10001];
    int spans[10001];
    int top;
} StockSpanner;

StockSpanner* stockSpannerCreate() {
    StockSpanner* obj = (StockSpanner*)malloc(sizeof(StockSpanner));
    obj->top = -1;
    return obj;
}

int stockSpannerNext(StockSpanner* obj, int price) {
    int span = 1;
    while (obj->top >= 0 && obj->prices[obj->top] <= price) {
        span += obj->spans[obj->top];
        obj->top--;
    }
    obj->top++;
    obj->prices[obj->top] = price;
    obj->spans[obj->top] = span;
    return span;
}

void stockSpannerFree(StockSpanner* obj) { free(obj); }

js

var StockSpanner = function () {
  this.stack = []
}

/**
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function (price) {
  let span = 1
  while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
    span += this.stack.pop()[1]
  }
  this.stack.push([price, span])
  return span
}

py

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

    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

• 时间复杂度：均摊 $O(1)$，每个元素最多入栈出栈一次
• 空间复杂度：$O(n)$

算法思路：

• 维护单调递减栈，栈中存 [price, span]
• 新价格入栈时，弹出所有 ≤ 当前价格的元素并累加其 span