Sliding Window Maximum
정수 배열 nums와 윈도우 크기 k가 주어집니다. 윈도우는 연속된 k개의 값을 포함합니다. 윈도우는 배열의 왼쪽 끝에서 시작해 한 번에 한 위치씩 오른쪽으로 이동하며, 오른쪽 끝이 마지막 값에 놓일 때까지 이동합니다.
왼쪽에서 오른쪽으로 각 위치의 윈도우 안에서 가장 큰 값으로 이루어진 배열을 반환하세요. 길이가 n인 배열에는 n-k+1개의 윈도우가 있으므로 결과에는 n-k+1개의 값이 들어갑니다.
함수
- numsinteger-array
- 배열에서 윈도우가 이동하는 범위
- kinteger
- 모든 윈도우에 있는 값의 개수
- 반환값integer-array
- 가장 왼쪽 윈도우부터 가장 오른쪽 윈도우까지 각 윈도우의 최댓값
제약 조건
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- 결과에는
nums.length-k+1개의 값이 왼쪽에서 오른쪽 순서로 창마다 하나씩 들어 있습니다.
예제
- 입력
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- 출력
- [12, 12, 12, 8, 8]
- 설명
- 12는 처음 세 개의 윈도우인
[4, 2, 12],[2, 12, 3],[12, 3, 8]에 들어 있습니다. 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은 정답을 하나 더 추가하지 않습니다.
제출 시 숨은 테스트 +15개
후속 질문
뒤쪽에 값을 추가하고, 앞쪽에서 값을 제거하며, 현재 최댓값을 각각 분할 상환 O(1) 시간에 읽을 수 있는 큐를 만들 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 윈도우를 훑어 최댓값을 찾으려면 윈도우마다
k단계가 필요합니다. 서로 이웃한 두 윈도우를 비교해 보세요. 왼쪽에서 값 하나가 빠지고 오른쪽에서 값 하나가 들어오기 때문에k-1개의 값을 공유합니다.새 값이 들어오면, 창에 있는 그 값보다 작거나 같은 모든 이전 값은 다시는 최댓값이 될 수 없습니다. 이전 값이 여전히 포함된 이후의 모든 창에는 새 값도 남아 있으며, 새 값은 이전 값보다 크거나 같기 때문입니다. 그런 이전 값들은 완전히 버려도 됩니다.
덱에서 살아남은 값들의 인덱스를 유지하고, 값이 앞에서 뒤로 갈수록 엄격히 감소하도록 합니다. 새 인덱스마다 뒤에서 더 작거나 같은 값들을 꺼내고, 해당 인덱스를 추가한 다음, 윈도우에서 벗어났다면 앞의 인덱스를 제거하고 앞에서 윈도우의 최댓값을 읽습니다.
풀이
인접한 윈도우는 k-1개의 값을 공유하므로, 각 최댓값을 처음부터 계산하면 거의 모든 작업을 반복하게 됩니다. 어려운 점은 최댓값은 되돌릴 수 없다는 것입니다. 가장 큰 값이 왼쪽으로 빠져나갈 때, 윈도우를 다시 읽지 않고도 그다음으로 큰 값을 찾아야 합니다. 단조 덱은 여전히 최댓값이 될 수 있는 값만 순서대로 유지하므로, 답은 항상 덱의 맨 앞에 있고 각 인덱스는 덱에 한 번 들어갔다가 한 번 나옵니다.
모든 창을 스캔하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
가장 직접적인 아이디어는 다음과 같은 명세에서 출발합니다. 인덱스 start에서 시작하는 윈도우는 start부터 start+k-1까지 포함합니다. 이 k개의 값을 읽고, 최댓값을 유지한 다음 시작 위치를 한 칸 오른쪽으로 옮깁니다. 시작 위치는 0부터 n-k까지 총 n-k+1개입니다.
정의에 따라 올바릅니다. 모든 윈도우를 빠짐없이 읽으므로 최댓값을 놓칠 수 없습니다. 결과를 제외하면 추가 메모리는 현재 최댓값을 저장하는 변수 하나입니다.
하지만 느립니다. n-k+1개의 각 윈도우를 처리하는 데 k번 읽어야 하며, 곱은 k가 n의 절반 정도일 때 가장 큽니다. n = 2 × 10^4이고 k = 10^4이면 10^4개의 윈도우에서 각각 10^4개의 값을 읽으므로 총 10^8번 읽게 됩니다. 더 나쁜 점은 이웃한 두 윈도우가 k-1개의 값을 공유하기 때문에, 읽기의 거의 대부분이 이미 읽은 값을 반복하는 것입니다.
알고리즘
- 빈 결과 목록을 만듭니다.
start를 0부터n-k까지 반복합니다.best를nums[start]로 설정한 다음,nums[start+k-1]까지의 모든 값과 비교하여 더 큰 값을 유지합니다.best를 결과에 추가합니다.- 결과를 반환합니다.
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까지 나누고, 이런 식으로 계속합니다. n이 k의 배수가 아니면 마지막 블록은 더 짧습니다. 윈도우의 길이는 정확히 k이므로, 하나의 블록과 일치하거나 한 블록의 끝부분과 다음 블록의 시작 부분을 포함합니다. 세 블록에 걸치는 경우는 없습니다.
이 방법을 위해 두 개의 배열을 사용합니다. fromStart[i]는 i가 속한 블록의 시작부터 i까지의 최댓값이며, 왼쪽에서 오른쪽으로 채우고 각 블록의 시작에서 초기화합니다. toEnd[i]는 i부터 해당 블록의 끝까지의 최댓값이며, 오른쪽에서 왼쪽으로 채우고 각 블록의 끝에서 초기화합니다. i에서 시작하는 윈도우는 i+k-1에서 끝납니다. 왼쪽 부분은 toEnd[i]가, 오른쪽 부분은 fromStart[i+k-1]가 포함하므로, 두 값 중 큰 값이 윈도우의 최댓값입니다. 윈도우가 블록 전체와 일치하면 두 부분 모두 그 블록의 최댓값이므로 답은 여전히 맞습니다.
nums = [4, 2, 12, 3, 8, 5, 1]이고 k = 3일 때, 블록은 [4, 2, 12], [3, 8, 5], [1]입니다. fromStart는 [4, 4, 12, 3, 8, 8, 1]이고 toEnd는 [12, 12, 12, 8, 8, 5, 1]입니다. 윈도우 [2, 12, 3]은 인덱스 1에서 시작합니다. toEnd[1] = 12는 2와 12를 포함하고, fromStart[3] = 3은 3을 포함하므로 답은 12입니다.
배열을 세 번 순회하므로 시간 복잡도는 O(n)입니다. 단점은 길이가 n인 보조 배열 두 개가 필요하고, 첫 번째 윈도우의 답을 구하기 전에 배열 전체가 있어야 한다는 점입니다.
알고리즘
fromStart를 왼쪽에서 오른쪽으로 채웁니다.i가k의 배수이면nums[i]를 복사하고, 그렇지 않으면fromStart[i-1]와nums[i]중 큰 값을 선택합니다.toEnd를 오른쪽에서 왼쪽으로 채웁니다.i가 마지막 인덱스이거나i+1이k의 배수이면nums[i]를 복사하고, 그렇지 않으면toEnd[i+1]과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가 여전히 포함된 이후의 모든 윈도우에는 i도 포함됩니다. i가 더 오른쪽에 있고 더 늦게 윈도우에서 빠지기 때문입니다. 그런 윈도우 모두에서 nums[i]는 적어도 그만큼 크므로, j는 더 이상 최댓값이 될 수 없습니다. i가 도착하는 순간 j는 쓸모가 없어지므로 버려도 됩니다.
버리지 않은 인덱스들을 덱에 보관하세요. i가 도착하면 뒤에서부터 값이 nums[i] 이하인 인덱스들을 꺼낸 다음 i를 넣습니다. 살아남은 인덱스들의 값은 앞에서 뒤로 갈수록 엄격히 감소합니다. 더 오래된 값이 더 크지 않았다면 이미 꺼냈을 것이기 때문입니다. 따라서 맨 앞에는 윈도우에서 가장 큰 값이 있습니다. 덱에는 값이 아니라 인덱스를 저장합니다. 윈도우가 지나가면 맨 앞의 인덱스도 빠져야 하기 때문입니다. i에서 끝나는 윈도우는 i-k+1에서 시작하므로, 빠져나간 인덱스는 i-k입니다. 이 인덱스가 맨 앞에 있으면 제거합니다.
nums = [4, 2, 12, 3, 8, 5, 1]과 k = 3을 따라가며 덱에 있는 값을 나열해 보겠습니다. 4가 들어옵니다: [4]. 2는 더 작으므로 그 뒤에서 기다립니다: [4, 2]. 12가 둘 다 꺼냅니다: [12]. 첫 번째 윈도우의 답은 12입니다. 3은 기다립니다: [12, 3]. 답은 12입니다. 8은 3을 꺼냅니다: [12, 8]. 답은 12입니다. 5는 기다립니다: [12, 8, 5]. 하지만 12는 인덱스 2에 있고, 인덱스 5에서 끝나는 윈도우는 인덱스 3에서 시작하므로 12는 빠져나갔습니다: [8, 5]. 답은 8입니다. 1은 기다립니다: [8, 5, 1]. 답은 8입니다.
왜 이것이 O(n)일까요? 내부 반복문은 한 단계에서 여러 인덱스를 꺼낼 수 있지만, 각 인덱스는 한 번 들어오고 최대 한 번만 꺼내집니다. 더 큰 값이 해당 인덱스보다 크면 뒤에서 꺼내고, 윈도우에서 빠져나가면 앞에서 꺼냅니다. 전체 실행에서 꺼내는 횟수는 모두 합쳐 최대 n번이므로, 총 작업량은 덱 연산 최대 2n번입니다. 덱의 모든 인덱스는 현재 윈도우 안에 있으므로, 덱에는 최대 k개의 인덱스만 들어갑니다.
알고리즘
- 인덱스를 저장할 빈 덱과 빈 결과 목록을 만듭니다.
- 각 인덱스
i에 대해 덱이 비어 있지 않고 덱의 마지막 인덱스에 해당하는 값이nums[i]이하인 동안 덱의 뒤에서 인덱스를 꺼냅니다. i를 덱의 뒤에 넣습니다.- 맨 앞 인덱스가
i-k와 같으면 윈도우에서 벗어난 것이므로 맨 앞에서 꺼냅니다. i ≥ k-1이면i에서 전체 윈도우가 끝납니다. 맨 앞 인덱스에 해당하는 값을 결과에 추가합니다.- 결과를 반환합니다.
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
함정과 경계 사례
대부분의 버그는 윈도우의 경계나 덱에 저장하는 값에서 발생합니다.
- 인덱스 대신 값을 저장하는 경우. 그러면 값이
nums[i-k]와 같을 때 맨 앞의 값을 만료시키게 되고, 중복 값이 있으면 문제가 생깁니다.[3, 1, 3]과k = 2에서 두 번째 3은 첫 번째 3을 제거하고, 자신도 제거됩니다. 윈도우에서 나간 값과 같기 때문입니다. 인덱스를 저장하고 맨 앞의 인덱스를i-k와 비교하세요. - 너무 일찍 또는 너무 늦게 답을 구하는 경우. 첫 번째 윈도우는
k가 아니라 인덱스k-1에서 끝나며, 결과에는 정확히n-k+1개의 값이 들어가야 합니다. - 잘못된 인덱스를 만료시키는 경우. 인덱스
i에서 끝나는 윈도우는i-k+1에서 시작하므로, 윈도우에서 나가는 인덱스는i-k입니다.i-k+1을 제거하면 아직 윈도우에 있는 값이 제거됩니다. - 빈 덱의 맨 뒤나 맨 앞을 읽는 경우. 맨 뒤의 값과 비교하기 전에 덱에 값이 있는지 확인하세요.
- 덱을 윈도우의 복사본처럼 취급하는 경우. 덱에는 후보만 들어 있으며, 인덱스의 개수는 1부터
k까지일 수 있으므로 덱의 크기로는 윈도우에 대해 아무것도 알 수 없습니다. - 블록 접근법에서 마지막 블록의 길이가
k보다 짧을 수 있다는 점을 잊는 경우. 오른쪽에서 왼쪽으로 진행하는 순회는 각 블록의 끝뿐 아니라 마지막 인덱스에서도 다시 시작해야 합니다.
자주 묻는 질문4
슬라이딩 윈도우 최댓값의 시간 복잡도는 얼마인가요?
모노토닉 덱을 사용하는 해법은 O(n) 시간에 실행됩니다. 각 인덱스는 한 번씩 추가되고 최대 한 번씩 제거되므로, 한 단계에서 여러 개를 제거할 수 있더라도 전체 실행 동안 내부 루프의 제거 횟수는 최대 n회입니다. 덱에는 인덱스가 최대 k개 들어가므로, 결과에 더해 필요한 추가 공간은 O(k)입니다.
슬라이딩 윈도 최댓값 문제를 힙으로 풀 수 있나요?
네. 값과 인덱스 쌍을 최대 힙에 넣으세요. 맨 위 항목을 읽기 전에, 인덱스가 윈도우 범위를 벗어난 동안 항목을 꺼내세요. 오래된 항목은 맨 위에 도달했을 때만 제거되기 때문입니다. 이 방법은 O(n log n) 시간에 실행되며 최대 n개의 항목을 보유할 수 있습니다. 덱은 더 큰 값이 들어오는 즉시 쓸모없는 값들을 제거하므로 더 빠르고 공간도 적게 사용합니다.
deque는 왜 값이 아니라 인덱스를 저장하나요?
윈도우가 앞쪽을 지나가면 앞쪽 원소를 제거해야 하며, 인덱스만이 이를 알려 줍니다. 값만으로는 nums[i-k]를 보고 추측해야 하는데, 같은 값이 두 번 이상 나타나면 이 방법은 실패합니다. 인덱스를 사용하면 추가 비용 없이 nums[index]로 값을 얻을 수도 있습니다.
단조 덱과 단조 스택의 차이점은 무엇인가요?
덱의 뒤쪽은 단조 스택처럼 작동합니다. 값을 푸시하기 전에, 그 값 때문에 쓸모없어지는 값들을 팝합니다. 덱은 너무 오래된 값을 위한 두 번째 출구를 앞쪽에 추가합니다. 다음으로 큰 원소를 찾는 것처럼 만료가 없는 문제에는 스택만 필요하지만, 슬라이딩 윈도우에는 양쪽 끝이 모두 필요합니다. 비교 연산자를 반대로 하면 같은 코드로 각 윈도우의 최솟값을 구할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def maxSlidingWindow(nums, k):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
기대값
[12, 12, 12, 8, 8]