유형별 정리/자료구조
자료구조O(n)

다음 큰 수 — 모노토닉 스택

각 원소의 오른쪽에서 처음 나오는 더 큰 수를, 스택 하나로 O(n)에 구해요.

이럴 때 써요

  • 각 원소의 '다음 큰 수' 또는 '이전 큰 수'를 구할 때
  • 오른쪽에서 처음으로 자기보다 큰(작은) 값이 언제 나오는지 물을 때
  • 매번 뒤를 다시 훑으면 O(n^2) 이라 시간 초과가 나는 문제일 때
  • 온도가 며칠 뒤 오르는지, 주가가 언제 회복되는지 같은 '기다림' 문제일 때

개념

아직 답(다음 큰 수)을 못 찾은 인덱스를 스택에 쌓아 둬요. 새 원소를 만날 때마다, 스택 맨 위가 가리키는 값보다 지금 값이 더 크면 그게 바로 그 원소의 답이에요. 답을 채우면서 pop 하고, 다 채웠으면 지금 인덱스를 push 해요.스택에는 항상 값이 단조 감소하는 인덱스들만 남아요(그래서 모노토닉이에요). 각 원소는 딱 한 번 들어가고 한 번 나오니, 전체가 O(n)이에요. 매번 뒤를 다시 훑는 O(n^2) 을 스택 하나로 없애는 거예요.
"[3, 1, 2, 4] 의 다음 큰 수" — 스택엔 인덱스를 쌓아요
nums = [3, 1, 2, 4]  ,  답 res = [-1, -1, -1, -1]
​
i=0 (3) :  스택 비어 있음  →  push 0        스택 [0]
i=1 (1) :  nums[0]=3 > 1  →  안 큼, push 1  스택 [0, 1]
i=2 (2) :  nums[1]=1 < 2  →  res[1]=2, pop  스택 [0]
          nums[0]=3 > 2  →  안 큼, push 2   스택 [0, 2]
i=3 (4) :  nums[2]=2 < 4  →  res[2]=4, pop  스택 [0]
          nums[0]=3 < 4  →  res[0]=4, pop   스택 []
          push 3                            스택 [3]
​
스택에 남은 3 은 답 없음  →  res = [4, 2, 4, -1]

패턴 코드

모노토닉 스택으로 다음 큰 수 구하기스택엔 아직 답을 못 찾은 인덱스만 남고, 값은 항상 단조 감소해요.
javascript
function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = []; // 아직 답을 못 찾은 인덱스들
  for (let i = 0; i < nums.length; i++) {
    // 지금 값이 스택 맨 위 값보다 크면, 그게 그 원소의 답이에요
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const j = stack.pop();
      res[j] = nums[i];
    }
    stack.push(i);
  }
  return res; // 스택에 남은 자리는 -1 그대로예요
}

이 유형으로 풀어보기

← 올바른 괄호 판별상위 K개·K번째 수 — 우선순위 큐 →