题目描述：

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

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

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

解法一：单调栈

算法思路：

根据题意，要求出每个 price 和上一个更大的元素的距离。比如示例中 70 的上一个更大元素是 80，距离为 2。

特别的，如果 price 比前面所有的数都要大，则返回当前是第几天。

对于每日价格 price，从这个价格往前找，找到第一个比这个价格大的价格，二者的下标差值 cnt 就是当日价格的跨度。

维护一个从栈底到栈顶价格单调递减的栈，栈中每个元素存放的是 (price, cnt) 数据对，其中 price 表示价格，cnt 表示当前价格的跨度。

对于出现的每一个价格 price，我们将其与栈顶元素进行比较，如果栈顶元素的价格小于等于 price ，则将当日价格的跨度 cnt 加上栈顶元素的跨度，然后将栈顶元素出栈，直到栈顶元素的价格大于 price 或者栈为空为止。

最后将 (price, cnt) 入栈，返回 cnt 即可。

代码实现：

class StockSpanner {
    private Deque<int[]> stk;
    public StockSpanner() {
        stk = new ArrayDeque<>();
    }
    
    public int next(int price) {
        int cnt = 1;
        while(!stk.isEmpty() && stk.peek()[0] <= price){
            cnt += stk.pop()[1];
        }
        stk.push(new int[] {price, cnt});
        return cnt;
    }
}

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

复杂度分析：

时间复杂度： O(n)，其中 n 为调用 next 函数的次数。

空间复杂度： O(n)，栈中最多有 n 个元素。

相关链接

• 901. 股票价格跨度

• 单调栈【基础算法精讲 26】