문제

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

---

입력

정수 배열 numbers

---

출력

모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return
단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

---

풀이

제한조건

• 4 ≤ numbers의 길이 ≤ 1,000,000
• 1 ≤ numbers[i] ≤ 1,000,000

접근방법

Stack (Monotone Stack)
단조증가 스택으로 구할 수 있다.

이중 for문을 사용하여 문제에서 요구하는 값들을 탐색할 수 있으나,
이는 O(N^2)의 방법으로 매우 비효율적인 방식이다.

Monotone Stack 단조스택
특정한 조건을 만족하는 원소들을 순서대로 유지하는 스택.
최대/최소 문제, 다음 큰 수, 다음 작은 수 같은 문제를 효율적으로 해결가능.

여기서는 스택의 원소들이 오름차순을 유지할 수 있도록 하는 단조증가 스택으로 구성한다.
즉, 스택의 맨 위에 있는 원소는 스택에서 가장 작은 원소인 것이다.

단, 여기서 생각해봐야할 점은 스택에 넣고자 하는 값이 원소의 값이 아닌 원소의 인덱스 라는 점이다. 원소의 값을 넣게 된다면, answer 배열에 값을 채울때, 어느 위치에 어떤 값이 채워져야할 지 모호해진다.

1. 현재 원소가 이전의 원소보다 작을 때 까지 stack에 수열의 index를 추가한다. 
2. 현재 원소가 스택의 top 원소를 인덱스로 하는 수열의 원소보다 큰 경우,
	stack의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔준다.

---

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int size = numbers.length;
        int[] answer = new int[size];
        Arrays.fill(answer, -1);
        
        Stack<Integer> s = new Stack();
        for(int i = 0; i < size; ++i){
            while(!s.isEmpty() && numbers[s.peek()] < numbers[i])
                answer[s.pop()] = numbers[i];
            s.add(i);
        }
        return answer;
    }
}