题目描述

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来 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]

题目分析

单调栈，从底到顶逐渐递减。
在入栈前，让栈中所有小于等于当前值的元素出栈，然后栈顶值的下标就是左侧第一个大于当前值的位置，从而计算出跨度。
可以在最左侧增加一个 Int.MAX_VALUE，用于处理栈底为空的情况。
栈中实际存储的是下标，而不是具体值。

Java

private List<Integer> list = new ArrayList<>();
private Deque<Integer> stack = new LinkedList<>();

public StockSpanner() {
    // 增加哨兵
    list.add(Integer.MAX_VALUE);
    stack.add(0);
}

public int next(int price) {
    int ans = 0;
    while (!stack.isEmpty() && list.get(stack.peek()) <= price) {
        stack.pop();
        ans = list.size() - stack.peek() - 1;
    }
    stack.push(list.size());
    list.add(price);
    return ans + 1;
}

Kotlin

private val list = ArrayList<Int>().apply {
    add(Int.MAX_VALUE)
}
private val stack = LinkedList<Int>().apply {
    push(0)
}

fun next(price: Int): Int {
    var ans = 0
    while (stack.isNotEmpty() && list[stack.peek()] <= price) {
        stack.pop()
        ans = list.size - stack.peek() - 1
    }
    stack.push(list.size)
    list.add(price)
    return ans + 1
}