[프로그래머스/Java] 뒤에 있는 큰 수 찾기

-Code

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        // 뒤에 수가 없으면 -1이 들어가야 하므로 -1로 채음
        Arrays.fill(answer, -1);
        // 단조 스택을 위한 덱
        Deque<Integer> deq = new ArrayDeque<>();
        // 덱의 피크 인덱스의 값과 비교해 나보다 큰고 가까운 값 넣기
        for (int i = 0; i < numbers.length; i++) {
            // 덱이 비어있지 않고 단조 스택의 peek 인덱스의 값이 
            // 현재 인덱스의 값보다 작은 경우 대입
            while(!deq.isEmpty() && numbers[deq.peekLast()] < numbers[i]) {
                answer[deq.pollLast()] = numbers[i];
            }
            // 나 자신도 검사해야 하므로 단조 스택에 넣기
            deq.addLast(i);
        }
        return answer;
    }
}

처음에는 2중 for문으로 O(n^2)으로 문제를 해결했으나 시간 초과문제가 생겼습니다.

그래서 힌트를 찾아보니 단조 스택이라는 것을 이용하는 문제였고 이를 이용해 현재 인덱스의 값보다 작은 경우 현재 값으로 대체하고 나를 넣어 다음부터 검사하도록 하여 해결했습니다.

이전에 단조 스택을 이용한 문제를 본 거 같은데 생각을 떠올리지 못해 아쉬웠습니다.