무한 알고리즘 의 주식 가격 범위 (단조 창고 + HashMap)

일부 주식 의 매일 가격 을 수집 하고 당일 가격 의 경 계 를 되 돌려 주 는 Stock Spanner 류 를 만 듭 니 다.
오늘 주식 가격 의 경 계 는 주식 가격 이 오늘 가격 보다 작 거나 같은 최대 연속 일수 로 정의 된다.
예 를 들 어 앞으로 7 일 동안 주식 의 가격 이 [100, 80, 60, 70, 60, 75, 85] 라면 주식 의 경 계 는 [1, 1, 1, 2, 1, 4, 6] 이 될 것 이다.
예시:
입력: ["StockSpanner", "next", "next", "next", "next", "next", "next", "next", "next"], [[], [100], [60], [60], [75], [85] 출력: [null, 1, 1, 1, 2, 1, 4, 6] 설명: 우선 S = StockSpanner () 를 초기 화 한 다음 S. next (100) 가 호출 되 고 1, S. next (80) 가 호출 되 고 1, S. next (60) 가 호출 되 고 1 로 되 돌아 갑 니 다.S. next (70) 가 호출 되 고 2 로 되 돌아 갑 니 다. S. next (60) 가 호출 되 고 1 로 되 돌아 갑 니 다. S. next (75) 가 호출 되 고 4 로 되 돌아 갑 니 다. S. next (85) 가 호출 되 고 6 으로 되 돌아 갑 니 다.
주의 (예 를 들 어) S. next (75) 는 4 를 되 돌려 줍 니 다. 왜냐하면 오늘 의 마지막 4 개 가격 (오늘 의 가격 포함 75) 이 오늘 의 가격 보다 작 거나 같 기 때 문 입 니 다.
알림:
StockSpanner. next (int price) 를 호출 할 때 1 < = price < = 10 ^ 5 가 있 습 니 다.각 테스트 용례 는 최대 10000 회 StockSpanner. next 를 호출 할 수 있 습 니 다.모든 테스트 용례 에서 최대 15000 회 StockSpanner. next 를 호출 합 니 다.이 문제 의 총 시간 제한 이 50 퍼센트 감소 했다.
생각:
단조 로 운 스 택, 맵 캐 시 이전의 결 과 를 이용 합 니 다.
문제 풀이:
class StockSpanner {
    HashMap<Integer, Integer> map; 
    Stack<Integer> s;
    public StockSpanner() {
        map = new HashMap<>();
        s= new Stack<>();
    }
    
    public int next(int price) {
        int result= 0;
        if(s.empty()){
            s.push(price);
            result=1;
            map.put(price,result);
            return result;
        }
        if(!s.empty()&&price<s.peek()){
            result=1;
            s.push(price);
        }else if(!s.empty()&&price>=s.peek()){
            result=1;
            while(!s.empty()&&price>=s.peek()){
                int temp=s.pop();
                int a=map.get(temp);
                result+=a;
            }
            s.push(price);
        }
        map.put(price,result);
        return result;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

좋은 웹페이지 즐겨찾기