Leetcode 在线股票跨度-java教程-PHP中文网

Leetcode 在线股票跨度

霞舞

发布： 2025-01-19 16:22:11

原创

426人浏览过

leetcode 在线股票跨度

解题思路

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

算法

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

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

复杂度分析

毕节热线企业建站系统6.0

毕节热线企业建站系统拥有一下系统功能，且具备完整后台，功能没有限制。一、公司介绍系统：将您的公司展现给广大用户，提高企业知名度。二、内容管理系统：可以发布新闻、公司动态等内容。三、产品展示系统：展示产品，同时提供在线订购功能。四、人才招聘系统：发布公司招聘信息，同时提供在线应聘功能。五、下载系统：支持下载分类。六、留言系统。七、投票系统。本次更新修改内容： 1.增加下载功能。 2

查看详情

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

代码实现

<code class="java">import java.util.ArrayList;
import java.util.List;

class StockSpanner {
    List<int[]> 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);
 */</code>

登录后复制

GitHub 仓库及 LeetCode 链接

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

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

以上就是Leetcode 在线股票跨度的详细内容，更多请关注php中文网其它相关文章！