문제 링크

문제 링크

문제 설명

제한 사항

입출력 예

입출력 예 설명

풀이

1. 제한사항에 배열의 길이는 최대 100만개이므로, 최대한 O(n)에 풀 생각을 하자
2. 문제는 곧 바로 다음 자기보다 크기가 큰 수를 찾는것인데, 이를 풀기위해 스택을 사용하였다.
3. 스택에는 현재 index를 저장하였는데, 스택을 사용하여 매번 루프마다 스택의 꼭대기에 위치한 numbers[peek()]가 현재 numbers보다 작은 숫자면 더 큰 수가 꼭대기에 위치할때까지 pop을하고 answer에 pop된 친구를 집어넣는다.
   3-1 pop은 방금 꺼낸 "값"을 리턴한다.
4. 마지막에 아직 스택에 값이 남아있다면, 이 index들은 자기 앞에 더 큰수가 없다는 것을 의미한다.
   4-1 메인 반복문을 나오고나서 전부 -1을 채워주자.

코드

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