Sliding Window Maximum

Q: Sliding Window Maximum의 시간 복잡도는 무엇인가요?

단조 덱 풀이의 시간 복잡도는 O(n) 입니다. 각 인덱스가 한 번씩 추가되고 최대 한 번씩 제거되기 때문입니다. 덱에는 최대 k 개의 인덱스가 들어가므로, 결과를 제외한 추가 공간 복잡도는 O(k) 입니다.

어려움슬라이딩 윈도우 단조 스택 큐

+10

정수 배열 nums와 윈도우 크기 k가 주어집니다. k개의 연속된 값으로 이루어진 윈도우는 왼쪽 끝에서 시작해 한 번에 한 위치씩 오른쪽으로 이동하며, 오른쪽 끝이 마지막 값에 놓일 때까지 움직입니다. 왼쪽에서 오른쪽으로 각 위치에서 윈도우 내 최댓값을 반환합니다. 길이가 n인 배열의 경우 n-k+1개의 값이 반환됩니다.

함수

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: 배열을 따라 이동하는 윈도우
kinteger: 모든 윈도우의 값 개수
반환값integer-array: 가장 왼쪽 창부터 가장 오른쪽 창까지 각 창의 최댓값

제약 조건

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
결과에는 왼쪽에서 오른쪽 순서로 각 윈도우당 하나씩 nums.length-k+1개의 값이 들어 있습니다.

예제

입력: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
출력: [12, 12, 12, 8, 8]
설명: 12는 처음 세 개의 윈도우 안에 있으므로, 각 윈도우의 답은 12입니다. 12가 윈도우에서 빠져나간 후에는 [3, 8, 5]와 [8, 5, 1] 모두 최댓값이 8입니다.

입력: nums = [-3, -1, -7, -2]k = 2
출력: [-1, -1, -2]
설명: 구간은 [-3, -1], [-1, -7] 및 [-7, -2]입니다. 두 음수 중 더 큰 수는 0에 더 가까운 수이므로, -1, -1 및 -2가 됩니다.

입력: nums = [6, 6, 1]k = 3
출력: [6]
설명: k가 배열의 길이와 같으면 윈도우는 하나이며, 배열 전체가 윈도우입니다. 가장 큰 값은 6이고, 두 번째 6은 두 번째 답을 추가하지 않습니다.

후속 질문

뒤쪽에 값을 추가하고, 앞쪽에서 값을 제거하며, 현재 최댓값을 각각 상환 O(1) 시간에 읽을 수 있는 큐를 만들 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

이웃한 윈도우는 k-1개의 값을 공유하므로, 각 최댓값을 다시 계산하면 작업 대부분을 반복하게 됩니다. 하지만 최댓값은 되돌릴 수 없습니다. 가장 큰 값이 윈도우에서 빠져나가면, 윈도우를 다시 읽지 않고도 그다음으로 큰 값을 알아야 합니다. 단조 덱은 여전히 최댓값이 될 수 있는 값만 유지하며, 정답은 맨 앞에 있습니다.

모든 창 스캔

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

각 윈도우의 k개 값을 읽고 가장 큰 값을 유지합니다. 각 윈도우를 모두 읽으므로 최댓값을 놓칠 수 없습니다. n-k+1개의 윈도우 각각을 읽는 데 k번의 읽기가 필요하며, k가 n의 절반 정도일 때 최악입니다. n = 2 × 10^4이고 k = 10^4이면, 값이 10^4개인 윈도우가 약 10^4개이므로 10^8번 읽게 됩니다.

알고리즘

start를 0부터 n-k까지 반복합니다.
nums[start]부터 nums[start+k-1]까지 중 가장 큰 값을 가져옵니다.
그 값을 결과에 추가하고, 반복문이 끝난 후 결과를 반환합니다.

def maxSlidingWindow(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        # Read all k values of this window again
        result.append(max(nums[i] for i in range(start, start + k)))
    return result

양쪽에서 최대값을 구하는 블록

핵심 아이디어

배열을 k 크기의 블록으로 나눕니다. 인덱스 0부터 k-1까지, 그다음 k부터 2k-1까지 나누고, 이런 식으로 이어집니다. k가 n을 나누어떨어지게 하지 않으면 마지막 블록은 더 짧을 수 있습니다. 윈도우의 길이는 정확히 k이므로, 윈도우는 블록 하나 전체이거나 한 블록의 끝부분과 다음 블록의 시작 부분으로 이루어집니다.

따라서 fromStart[i]에는 i가 속한 블록의 시작부터 i까지의 최댓값을, toEnd[i]에는 i부터 블록의 끝까지의 최댓값을 미리 계산합니다. 인덱스 i에서 시작하는 윈도우는 i+k-1에서 끝납니다. toEnd[i]는 윈도우의 왼쪽 부분을, fromStart[i+k-1]는 오른쪽 부분을 다루므로, 둘 중 큰 값이 윈도우의 최댓값입니다. 첫 번째 예시에서 윈도우 [2, 12, 3]은 toEnd[1] = 12와 fromStart[3] = 3을 사용하므로, 최댓값은 12입니다.

세 번의 순회로 O(n) 시간에 실행할 수 있습니다. 대신 길이가 n인 보조 배열 두 개가 필요하고, 첫 번째 결과를 내기 전에 배열 전체가 있어야 합니다.

알고리즘

fromStart를 왼쪽에서 오른쪽으로 채우고, i가 k의 배수일 때 nums[i]로 다시 시작합니다.
toEnd를 오른쪽에서 왼쪽으로 채우고, 마지막 인덱스와 i+1이 k의 배수인 위치에서 nums[i]로 다시 시작합니다.
0부터 n-k까지의 모든 시작 위치 i에 대해 toEnd[i]와 fromStart[i+k-1] 중 더 큰 값을 추가합니다.

def maxSlidingWindow(nums, k):
    n = len(nums)
    # Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
    from_start = [0] * n  # max from the start of i's block up to i
    to_end = [0] * n      # max from i up to the end of i's block
    for i in range(n):
        if i % k == 0:
            from_start[i] = nums[i]
        else:
            from_start[i] = max(from_start[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            to_end[i] = nums[i]
        else:
            to_end[i] = max(to_end[i + 1], nums[i])
    # A window [i, i+k-1] is the tail of one block plus the head of the next.
    return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]

인덱스의 단조 덱

핵심 아이디어

인덱스 j가 i보다 앞에 있고 nums[j] ≤ nums[i]라면, j는 더 이상 최댓값이 될 수 없습니다. j를 포함하는 이후의 모든 윈도우에는 나중에 빠져나가는 i도 포함되기 때문입니다. 따라서 i가 오면 j를 잊어도 됩니다.

아직 잊히지 않은 인덱스들을 덱에 보관합니다. i가 오면 덱의 뒤에서 값이 nums[i] 이하인 인덱스들을 제거한 다음 i를 추가합니다. 남은 값들은 앞에서 뒤로 갈수록 엄격히 감소하므로 맨 앞이 윈도우의 최댓값입니다. 윈도우가 맨 앞의 인덱스를 지나면 그 인덱스도 빠져나가야 하므로 인덱스를 저장합니다. 첫 번째 예시에서 인덱스 5일 때 덱에는 12, 8, 5가 들어 있습니다. 12는 인덱스 5 - 3 = 2에 있으므로 빠져나가고, 답은 8입니다.

각 인덱스는 한 번 추가되고 최대 한 번 제거됩니다. 덱 연산은 최대 2n회이므로 시간 복잡도는 O(n)입니다. 덱에는 최대 k개의 인덱스만 저장됩니다.

알고리즘

각 인덱스 i에 대해, 덱이 비어 있지 않고 덱의 마지막 값이 nums[i] 이하인 동안 뒤에서 인덱스를 꺼냅니다.
i를 뒤에 넣습니다.
맨 앞 인덱스가 i-k와 같으면, 해당 인덱스는 윈도우를 벗어난 것이므로 꺼냅니다.
i ≥ k-1이면, 맨 앞 인덱스의 값을 결과에 추가합니다.

from collections import deque


def maxSlidingWindow(nums, k):
    window = deque()  # indices; their values strictly decrease from front to back
    result = []
    for i, x in enumerate(nums):
        # A value at the back that is not bigger than x can never be a maximum again.
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        # The front index has slid out of the window on the left.
        if window[0] == i - k:
            window.popleft()
        # From index k-1 on, every step completes a window; its maximum sits at the front.
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

함정과 경계 사례

인덱스가 아닌 값을 저장하는 경우. [3, 1, 3]과 k = 2에서 두 번째 3은 첫 번째 3을 꺼내고, 그다음 자신도 값이 나간 nums[0]과 같으므로 제거됩니다.
너무 일찍 또는 너무 늦게 답을 내는 경우. 첫 번째 전체 윈도는 인덱스 k-1에서 끝나며, 결과에는 정확히 n-k+1개의 값이 있어야 합니다.
i-k 대신 i-k+1을 만료시키는 경우. 그 인덱스는 아직 윈도의 첫 번째 값입니다.
덱에 값이 있는지 확인하지 않고 덱의 뒤쪽을 읽는 경우.
블록 방식에서 마지막 블록이 k보다 짧을 수 있다는 점을 잊는 경우. 오른쪽에서 왼쪽으로의 순회는 마지막 인덱스와 각 블록의 끝에서 모두 다시 시작해야 합니다.

자주 묻는 질문3

Sliding Window Maximum의 시간 복잡도는 무엇인가요?

단조 덱 풀이의 시간 복잡도는 O(n)입니다. 각 인덱스가 한 번씩 추가되고 최대 한 번씩 제거되기 때문입니다. 덱에는 최대 k개의 인덱스가 들어가므로, 결과를 제외한 추가 공간 복잡도는 O(k)입니다.

슬라이딩 윈도우 최댓값 문제를 힙으로 풀 수 있을까요?

네. 값과 인덱스 쌍을 최대 힙에 넣고, 맨 위 값을 읽기 전에 인덱스가 윈도우 밖에 있으면 해당 항목을 꺼내세요. 이 방식은 O(n log n) 시간에 실행되며 최대 n개의 항목을 저장할 수 있습니다. 덱은 더 큰 값이 들어오는 즉시 쓸모없는 값을 제거하므로 더 빠르고 공간도 적게 사용합니다.

단조 덱과 단조 스택의 차이점은 무엇인가요?

덱의 뒤쪽은 단조 스택처럼 작동합니다. 값을 푸시하기 전에, 그 값 때문에 쓸모없어진 값들을 팝합니다. 덱은 너무 오래된 값을 위한 앞쪽 출구를 추가합니다. 다음으로 큰 원소에는 만료 조건이 없으므로 스택만 있으면 됩니다. 비교를 뒤집으면 덱은 각 윈도우의 최솟값을 구합니다.

def maxSlidingWindow(nums, k):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

예상 출력

[12, 12, 12, 8, 8]

Sliding Window Maximum

함수

제약 조건

예제

힌트

풀이

모든 창 스캔

양쪽에서 최대값을 구하는 블록

인덱스의 단조 덱

함정과 경계 사례

자주 묻는 질문3

비슷한 문제