力扣。線上庫存跨度

解題思路

能否利用先前計算出的跨度結果？

方法

將股票價格及其跨度保存在陣列中。

當最後一天的價格小於目前價格時，跳到最後一天跨度的日期。

複雜度

• 時間複雜度：O(n)
• 空間複雜度：O(n)

代碼

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

更多解法請造訪GitHub倉庫：Git LeetCode個人主頁：LeetCode: devn007

以上是力扣。線上庫存跨度的詳細內容。更多資訊請關注PHP中文網其他相關文章！