题目描述

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

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

• 例如，如果未来 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 次。

算法

(单调栈) $O(n)$

1. 这道题的本质是寻找每个数左边第一个比它严格大的数字。
2. 故可以采用单调栈的思想，维护一个单调递减的栈，栈中存放数字的下标。
3. 每次新加入一个数字时，若栈顶小于等于当前数字，则出栈直到栈空或者栈顶严格大于当前数字；
4. 则栈顶距离新插入数字的下标的距离就是答案，然后将新数字压栈。

时间复杂度

• 每个数字最多进栈一次出栈一次，故时间复杂度为 $O(n)$。

C++ 代码

class StockSpanner {
private:
    vector<int> prices;
    int counter;
    stack<int> s;

public:
    StockSpanner() {
        counter = 0;
    }

    int next(int price) {
        int ans;
        while (!s.empty() && prices[s.top()] <= price)
            s.pop();

        if (s.empty()) ans = counter + 1;
        else ans = counter - s.top();

        prices.push_back(price);
        s.push(counter);

        counter++;
        return ans;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */