LeetCode 901. 股票价格跨度 中等

作者:Choi Yang

更新于:7 个月前

字数统计:763 字

阅读时长:3 分钟

题目描述

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

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

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

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：

调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用  10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。

解题思路

正如题意，我们要求当前元素之前，比自己小（可以相等）的元素个数，并且元素个数包括本身，那么我们最后的结果应该还要加 1.

于是按题意，我们采用跨度法，举个例子，对于例子 6，1，2，3，4，9，从后往前逆推一下，当我们新插入 9 的时候，如果发现前一位的 4 比 9 小，那么是否说明比 9 小的数量就等于比 4 小的数量加 1？然而这是错的，因为首位的 6 比 9 小，却比 4 大，因此截止数字的 4 时候，比 4 小的数量中并不包含 6 与 9 的对比。

因此，我们还要跳到 6 的位置再去计算小于等于自己的元素。

javascript

var StockSpanner = function () {
  // 存储股票跨度
  this.spanner = [];
  // 存储股票价格
  this.stockPrice = [];
};

/**
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function (price) {
  // 对于第一天进行特殊判断
  if (!this.spanner.length) {
    this.spanner.push(1);
    this.stockPrice.push(price);
    // 直接返回1
    return 1;
  }
  let cnt = 0;
  let idx = this.stockPrice.length - 1;
  while (price >= this.stockPrice[idx] && idx >= 0) {
    cnt += this.spanner[idx];
    idx -= this.spanner[idx];
  }
  // 加上本身
  cnt++;
  // 进行更新操作，将当前股票价格和跨度入栈
  this.spanner.push(cnt);
  this.stockPrice.push(price);
  return cnt;
};

cpp

class StockSpanner {
public:
    StockSpanner() {

    }

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

private:
    stack<pair<int, int>> s;
};

java

class StockSpanner {
    Stack<Integer> prices, weights;

    public StockSpanner() {
        prices = new Stack();
        weights = new Stack();
    }

    public int next(int price) {
        int w = 1;
        while (!prices.isEmpty() && prices.peek() <= price) {
            prices.pop();
            w += weights.pop();
        }

        prices.push(price);
        weights.push(w);
        return w;
    }
}

python

class StockSpanner:

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

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

学如逆水行舟，不进则退

Contributors

Choi Yang