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)