力扣。在线库存跨度

解题思路

能否利用之前计算出的跨度结果？

方法

将股票价格及其跨度保存在数组中。

当最后一天的价格小于当前价格时，跳转到最后一天跨度的日期。

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

代码

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

class StockSpanner {
    ArrayList<Pair<Integer, Integer>> list;

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

    public int next(int price) {
        int index = list.size() - 1;
        int ans = 1;
        while (index != -1) {
            if (list.get(index).getKey() > price) break;
            int span = list.get(index).getValue();
            ans += span;
            index -= span;
        }
        list.add(new Pair<>(price, ans));
        return ans;
    }
}

//假设Pair类已定义
class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}


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

更多解法请访问GitHub仓库：Git LeetCode个人主页：LeetCode: devn007

以上是力扣。在线库存跨度的详细内容。更多信息请关注PHP中文网其他相关文章！