Letcode . Stok Dalam Talian

Idea penyelesaian masalah

Bolehkah saya menggunakan hasil span yang dikira sebelum ini?

Kaedah

Simpan harga saham dan rentangnya dalam tatasusunan.

Apabila harga hari terakhir kurang daripada harga semasa, lompat ke tarikh rentang hari terakhir.

Kerumitan

• Kerumitan masa: O(n)
• Kerumitan ruang: O(n)

Kod

<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>

Untuk lebih banyak penyelesaian, sila lawati repositori GitHub: Git Halaman utama peribadi LeetCode: LeetCode: devn007

Atas ialah kandungan terperinci Letcode . Stok Dalam Talian. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!