[프로그래머스 알고리즘 고득점 Kit][스택/큐][Java] 주식가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

스택에는 아직 가격이 떨어진 시점을 찾지 못한 인덱스를 저장한다.

현재 가격이 스택 맨 위 인덱스의 가격보다 낮다면, 해당 주식은 현재 시점에 처음 가격이 떨어진 것이다.

answer[lastIdx] = i - lastIdx;

 

가격이 떨어진 인덱스를 계속 제거하기 때문에 스택의 가격은 아래에서 위로 비감소 순서를 유지한다.

전체 순회 후 스택에 남은 인덱스는 끝까지 가격이 떨어지지 않은 경우이므로 마지막 시점까지의 시간을 계산한다.

answer[idx] = prices.length - 1 - idx;

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] answer = new int[len];
        ArrayDeque<Integer> st = new ArrayDeque<>();
        st.addLast(0);
        for(int i=1; i<prices.length; i++) {
            while(!st.isEmpty() && prices[i] < prices[st.peekLast()]) {
                int lastIdx = st.pollLast();
                answer[lastIdx] = i - lastIdx;
            }
            
            st.addLast(i);
        }
        while(!st.isEmpty()) {
            int idx = st.pollLast();
            answer[idx] = prices.length - idx - 1;
        }
        return answer;
    }
}