← 10주차 · 스택 · 큐 · 덱
어려움스택단조 스택

다음 큰 원소

정수 배열 nums가 주어져요. 각 원소마다 그 오른쪽에서 처음으로 나타나는 자기보다 큰 값을 찾아, 같은 자리에 담은 배열로 반환해요. 오른쪽에 더 큰 값이 없으면 그 자리에는 -1을 넣어요.

예를 들어 [2, 1, 3]에서 2의 다음 큰 값은 3, 1의 다음 큰 값도 3, 3은 오른쪽에 더 큰 값이 없어서 -1이에요.

모든 쌍을 하나하나 비교하면 O(n²)이지만, 단조 스택을 쓰면 각 원소가 스택에 한 번 들어갔다 한 번 나오면서 O(n)으로 풀 수 있어요.

예시

예시 1
입력
nums = [2, 1, 3]
출력
[3, 3, -1]
예시 2
입력
nums = [5, 4, 3, 2, 6]
출력
[6, 6, 6, 6, -1]
설명
앞의 네 값은 모두 마지막 6에서 처음으로 더 큰 값을 만나요.

제한 사항

  • 1 ≤ nums.length ≤ 100,000
  • -10^9 ≤ nums[i] ≤ 10^9
스택에 아직 답을 못 찾은 원소들의 인덱스를 담아 둬요. 새 값을 볼 때, 스택 맨 위 원소보다 크면 그 원소의 답이 지금 확정되니 꺼내서 채워요. 더 이상 큰 관계가 아니면 현재 인덱스를 스택에 넣어요. 끝까지 남은 인덱스들은 답이 -1이에요.
javascript
function nextGreaterElement(nums) {
  const answer = new Array(nums.length).fill(-1);
  const stack = [];
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      answer[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return answer;
}
이전 문제후위 표기식 계산
다음 문제이진 탐색
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.