쉽게 생각해내기는 어려운 풀이라고 생각한다.

풀이

1. 이전 가격보다 높을 경우, 큐에 인덱스를 저장한다.
   1-1. 가격이 떨어진 경우, 현재 시간 - 스택 최상위 인덱스(마지막으로 높았던 가격) 를 정답 배열에 저장한다.
   1-2. 스택을 하나 지운다.
2. 스택에 남아있는 가격 인덱스는 떨어지지 않았다는 얘기 이다.
   2-1. 전체 길이 - 인덱스 를 정답 배열에 저장한다.

전체코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> st = new Stack<>();
        
        for(int i = 0; i < prices.length; i++) {
            while(!st.isEmpty() && prices[i] < prices[st.peek()]) {
                answer[st.peek()] = i - st.peek();
                st.pop();
            }
            
            st.push(i);
        }
        
        while (!st.isEmpty()) {
            answer[st.peek()] = prices.length - st.peek() - 1;
            st.pop();
        }
        
        return answer;
    }
}

떨어지는 가격

for(int i = 0; i < prices.length; i++) {
	while(!st.isEmpty() && prices[i] < prices[st.peek()]) {
		answer[st.peek()] = i - st.peek();
		st.pop();
	}
    
	st.push(i);
}

• 0초는 당연히 떨어질 수 없으니 인덱스가 저장된다.
• 1초부터는 그전 가격과 비교한다. 이전 보다 가격이 높을 경우 인덱스를 스택에 쌓는다.
• 가격이 낮을 경우, 정답 배열에 현재 시간 - 스택 peek() 값 을 저장하고, pop() 한다.
  현재가격이 더 높은 시점이 될때 까지 반복한다.

떨어지지 않은 가격

while (!st.isEmpty()) {
	answer[st.peek()] = prices.length - st.peek() - 1;
	st.pop();
}

• ex) 1초 부터 끝까지(4초) 유지 했다면 4 - 1 = 3초가 정답배열의 1초 인덱스에 저장이 된다.
• 저장할때 -1을 한 이유는, 배열을 1부터가 아니라 0부터 시작했기 때문이다.