Leetcode . Online Stock Span

Problem-solving ideas

Can I use the previously calculated span results?

Method

Save the stock price and its span in an array.

When the price of the last day is less than the current price, jump to the date of the last day span.

Complexity

• Time complexity: O(n)
• Space complexity: 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);
 */

For more solutions, please visit the GitHub repository: Git LeetCode personal homepage: LeetCode: devn007

The above is the detailed content of Leetcode . Online Stock Span. For more information, please follow other related articles on the PHP Chinese website!