496. Next Greater Element I

리트코드 496번 풀이

문제

Next Greater Element I

풀이 1

아이디어

nums2를 먼저 순회하면서 각 원소의 next greater element를 Map에 미리 저장해두고, nums1의 각 원소를 Map에서 O(1)로 조회해 결과를 만든다.

내부 루프에서 처음 next greater를 찾는 순간 break하는 것이 핵심. (까먹고 빼먹어서 한참 헤맸다.) 빠져나오지 않으면 더 큰 값으로 계속 덮어쓰게 된다.

코드

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const ans: number[] = [];
  const numMap = new Map<number, number>();

  for (let i = 0; i < nums2.length; i++) {
    const num = nums2[i];
    for (let j = i + 1; j < nums2.length; j++) {
      if (num < nums2[j]) {
        numMap.set(num, nums2[j]);
        break;
      }
    }
    if (!numMap.has(num)) numMap.set(num, -1);
  }

  for (const num of nums1) {
    ans.push(numMap.get(num)!);
  }

  return ans;
}

시간 / 공간 복잡도

• 시간 복잡도: O(m × n) — nums2 이중 루프 (m: nums1 길이, n: nums2 길이)
• 공간 복잡도: O(n) — Map 저장 공간

풀이 2

아이디어

Follow up: Could you find an O(nums1.length + nums2.length) solution?

리트코드의 도발로 찾아본 Monotonic Stack(단조 스택) 풀이.

nums2를 순회하면서 “아직 next greater를 못 찾은 원소들”을 스택에 쌓아둔다. 현재 원소가 스택 top보다 크면 top의 next greater가 현재 원소로 확정되기 때문에 pop하며 Map에 저장한다. 순회가 끝난 뒤 스택에 남은 원소들은 next greater가 없으므로 -1로 처리한다.

각 원소는 스택에 정확히 1번 push되고 1번 pop되므로 전체 O(n)이다.

코드

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const ans: number[] = [];
  const stack: number[] = [];
  const map = new Map<number, number>();

  // 1. 단조증가스택을 이용해서 map을 채우기
  for (const num of nums2) {
    while (stack.length > 0 && stack[stack.length - 1] < num) {
      // stack의 top이 num보다 작은 경우, top의 next greater가 num이 된다.
      map.set(stack[stack.length - 1], num);
      stack.pop();
    }
    // 다 채웠으면 현재 원소는 stack에 (나중 루프에서 map을 채운다.)
    stack.push(num);
  }

  // 2. 여전히 스택에 남아있는 원소들은 next greater가 없는 원소들
  for (const num of stack) {
    map.set(num, -1);
  }

  // 3. 정답 배열 만들기
  for (const num of nums1) {
    ans.push(map.get(num)!);
  }

  return ans;
}

시간 / 공간 복잡도

• 시간 복잡도: O(m + n) — nums2 순회 O(n) + nums1 조회 O(m)
• 공간 복잡도: O(n) — 스택 + Map