Leetcode . Online-Lagerspanne

Ideen zur Problemlösung

Kann ich die zuvor berechneten Span-Ergebnisse verwenden?

Methode

Speichern Sie den Aktienkurs und seine Spanne in einem Array.

Wenn der Preis des letzten Tages niedriger ist als der aktuelle Preis, springen Sie zum Datum des letzten Tages.

Komplexität

• Zeitliche Komplexität: O(n)
• Raumkomplexität: O(n)

Code

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

Weitere Lösungen finden Sie im GitHub-Repository: Git Persönliche LeetCode-Homepage: LeetCode: devn007

Das obige ist der detaillierte Inhalt vonLeetcode . Online-Lagerspanne. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!