239. 슬라이딩 윈도우 최대값

문제 설명

정수 배열 nums가 주어졌을 때, 크기 k의 슬라이딩 윈도우가 배열의 가장 왼쪽에서 가장 오른쪽으로 이동합니다. 윈도우 내의 k개의 숫자만 볼 수 있습니다. 윈도우는 매번 오른쪽으로 한 칸씩 움직입니다.

윈도우 내의 최대값을 반환하세요.

예제 1:

<strong>입력:</strong> nums = [1,3,-1,-3,5,3,6,7], k = 3
<strong>출력:</strong> [3,3,5,5,6,7]
<strong>설명:</strong>
윈도우 위치                최대값
---------------               -----
[1  3  -1] -3  5  3  6  7       <strong>3</strong>
 1 [3  -1  -3] 5  3  6  7       <strong>3</strong>
 1  3 [-1  -3  5] 3  6  7      <strong>5</strong>
 1  3  -1 [-3  5  3] 6  7       <strong>5</strong>
 1  3  -1  -3 [5  3  6] 7       <strong>6</strong>
 1  3  -1  -3  5 [3  6  7]      <strong>7</strong>

예제 2:

<strong>입력:</strong> nums = [1], k = 1
<strong>출력:</strong> [1]

문제 해결 방법: 단조 큐 (Monotonic Queue)

**줄어드는 양방향 큐 q**를 사용하여 현재 윈도우 내에서 최대값이 될 수 있는 원소의 인덱스를 유지합니다.

• 큐의 머리 부분은 항상 현재 윈도우 내의 최대값 인덱스를 담습니다.
• 윈도우를 이동할 때마다:
• 윈도우 왼쪽 밖으로 벗어난 인덱스를 제거합니다.
• 현재 원소보다 작은 값을 가진 큐의 끝 인덱스들을 제거합니다.
• 윈도우가 형성된 후, 결과에 최대값을 저장합니다.

Python 코드

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        mono_q = deque()  # 현재 윈도우 내 최대값 후보를 저장하는 단조 큐
        result = []       # 각 윈도우의 최대값 저장

        for i in range(len(nums)):
            # 윈도우 왼쪽 밖으로 벗어난 인덱스 제거
            if mono_q and mono_q[0] < i - k + 1:
                mono_q.popleft()

            # 큐의 끝에서 현재 원소보다 작은 값을 가진 인덱스 제거
            while mono_q and nums[mono_q[-1]] < nums[i]:
                mono_q.pop()

            # 현재 인덱스를 큐에 추가
            mono_q.append(i)

            # 윈도우가 완전히 형성된 경우 최대값 저장
            if i >= k - 1:
                result.append(nums[mono_q[0]])

        return result

시간 복잡도와 공간 복잡도

예제 설명

nums = [1,3,-1,-3,5,3,6,7], k = 3 예제에 대하여:

• 첫 번째 윈도우: [1,3,-1] → 최대값 3
• 두 번째 윈도우: [3,-1,-3] → 최대값 3
• 세 번째 윈도우: [-1,-3,5] → 최대값 5
• ...

출력 결과: [3,3,5,5,6,7]

요약

• 이 문제는 슬라이딩 윈도우와 단조 큐를 활용한 고전적인 문제입니다.
• 큐를 통해 시간복잡도를 O(nk)에서 O(n)으로 최적화합니다.
• 시간 제한이 있는 문제나 시간 창, 구간 최대/최소값 유형의 문제에 자주 사용됩니다.