リートコード 。オンライン在庫スパン

問題解決のアイデア

以前に計算したスパン結果を使用できますか?

メソッド

株価とそのスパンを配列に保存します。

最終日の価格が現在の価格より低い場合、最終日のスパンの日付にジャンプします。

複雑さ

• 時間計算量: 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 中国語 Web サイトの他の関連記事を参照してください。