Leetcode 在线股票跨度

最近发现不少小伙伴都对文章很感兴趣，所以今天继续给大家介绍文章相关的知识，本文《Leetcode 在线股票跨度》主要内容涉及到等等知识点，希望能帮到你！当然如果阅读本文时存在不同想法，可以在评论中表达，但是请勿使用过激的措辞~

解题思路

能否利用之前的计算结果来优化？答案是肯定的。

算法

使用数组存储股票价格及其对应的跨度。

当新价格小于前一日价格时，可直接利用之前计算的跨度结果，避免重复计算。

复杂度分析

• 时间复杂度：O(n) 每次next操作最坏情况下遍历整个数组，但平均时间复杂度为O(1)。
• 空间复杂度：O(n) 存储价格和跨度的数组大小与输入数据量成正比。

代码实现

import java.util.ArrayList;
import java.util.List;

class StockSpanner {
    List list;

    public StockSpanner() {
        list = new ArrayList<>();
    }

    public int next(int price) {
        int span = 1;
        int index = list.size() - 1;
        while (index >= 0 && list.get(index)[0] <= price) {
            span += list.get(index)[1];
            index -= list.get(index)[1];
        }
        list.add(new int[]{price, span});
        return span;
    }
}

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

GitHub 仓库及 LeetCode 链接

更多解法请访问 GitHub 仓库：GitHub 仓库链接

LeetCode 题目链接：LeetCode 题目链接 (devn007)

终于介绍完啦！小伙伴们，这篇关于《Leetcode 在线股票跨度》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！