Leetcode 在线股票跨度

wufei123 2025-01-26 阅读:40 评论:0

解题思路能否利用之前的计算结果来优化？答案是肯定的。算法使用数组存储股票价格及其对应的跨度。当新价格小于前一日价格时，可直接利用之前计算的跨度结果，避免重复计算。复杂度分析时间复杂度：O(n) 每次next操作最坏情况下遍...

leetcode 在线股票跨度

解题思路

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

算法

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

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

复杂度分析

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

代码实现

PHP

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);
 */