Leetcode. Durée du stock en ligne

Idées de résolution de problèmes

Puis-je utiliser les résultats de span calculés précédemment ?

Méthode

Enregistrez le cours de l'action et sa durée dans un tableau.

Lorsque le prix du dernier jour est inférieur au prix actuel, passez à la date du dernier jour.

Complexité

• Complexité temporelle : O(n)
• Complexité spatiale : O(n)

Code

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

Pour plus de solutions, veuillez visiter le référentiel GitHub : Git Page d'accueil personnelle de LeetCode : LeetCode : devn007

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!