股票价格跨度｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看<活动链接>

一、题目描述

编写一个 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) 小于或等于今天的价格。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/online-stock-span
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

提示：

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

二、思路分析

题目给了我们一个股票价格列表，并让求股票价格小于或等于今天价格的最大连续日数（往前面的日子数）。也就是说判断结束的条件是：今天的价格比前面的价格小。

是不是感到非常熟悉？列表里的价格是有序的，这是我们之前遇到过的单调栈。这个栈从栈顶到栈尾是一个单调递增栈。

三、AC代码

class StockSpanner {

    private List<Integer> prices;
    private Stack<Integer> indexStack;
    private int index;

    public StockSpanner() {
        prices = new Stack<>();
        indexStack = new Stack<>();
        index = 0;
    }
    
    public int next(int price) {
        while(!indexStack.empty()&&prices.get(indexStack.peek())<=price) {
            indexStack.pop();
        }
        prices.add(price);
        int res = indexStack.empty() ? index + 1 : index - indexStack.peek();
        indexStack.push(index);
        index++;
        return res;
    }
}
复制代码

四、总结

又是一道单调栈的题目，初次遇到这种题目还是没什么思路的，但是做过几道以后发现套路都是类似的。无非就是先选择遍历方式，再决定什么时候结束循环。最终通过索引计算出相差的时间或天数。