리트코드 . 온라인 주식 범위

문제 해결 아이디어

이전에 계산된 스팬 결과를 사용할 수 있나요?

방법

주가와 그 범위를 배열로 저장합니다.

마지막 날의 가격이 현재 가격보다 낮을 경우, 마지막 날의 날짜로 이동합니다.

복잡성

• 시간 복잡도: 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!