이 문제의 핵심은 모든 원소의 순위를 계속 보관하는 것이 아니라, 앞으로의 구간 최댓값이 될 가능성이 남은 인덱스만 보관하는 데 있습니다. 후보의 값과 만료 시점을 덱의 서로 다른 끝에서 관리하면 겹치는 구간을 다시 정렬하지 않고도 각 입력을 한 번씩 처리할 수 있습니다.
오래된 큰 값과 새로운 작은 값의 수명 차이
배열 [4,2,3,1,5]에서 길이 3인 각 연속 구간의 최댓값은 [4,3,5]입니다. 구간마다 정렬하면 겹치는 원소를 계속 다시 정렬합니다. 대신 앞으로 최댓값이 될 수 있는 후보만 덱(deque)에 남길 수 있습니다.
덱 앞에서는 구간을 벗어난 오래된 인덱스를 지우고, 뒤에서는 새 값보다 작거나 같은 후보를 지웁니다. 서로 다른 이유로 양끝을 사용하기 때문에 일반 스택만으로는 부족합니다.
뒤의 작은 후보 제거의 지배 관계
위치 1의 값 2 뒤에 위치 2의 값 3이 들어왔다고 합시다. 앞으로 구간의 오른쪽 끝이 전진하는 동안 2가 포함된 구간에 3도 포함됩니다. 3은 더 크고 더 늦게 만료됩니다. 그러므로 2는 다시 최댓값이 될 수 없습니다.
반면 위치 0의 값 4는 새 값 3보다 크므로 남겨야 합니다. 다만 구간 왼쪽 끝이 1로 옮겨가면 4는 아무리 커도 범위 밖이므로 제거합니다. 값의 우열과 시간 범위의 만료를 따로 검사해야 합니다.
그림을 글로 읽기
- 구간 밖 앞 인덱스 제거: index <= i-K
- 뒤의 작거나 같은 값 제거: 더 새롭고 큰 값이 대신함
- 현재 인덱스 i 삽입
- 덱 앞의 값을 반환: 구간이 K개 찼을 때
- 구간 밖 앞 인덱스 제거 → 뒤의 작거나 같은 값 제거: 유효 범위
- 뒤의 작거나 같은 값 제거 → 현재 인덱스 i 삽입: 후보 단조성
- 현재 인덱스 i 삽입 → 덱 앞의 값을 반환: 최댓값 조회
예제 구간별 덱 상태 추적
| i·값 | 제거 | 덱 인덱스 | 덱 값 | 출력 |
|---|---|---|---|---|
| 0·4 | 없음 | [0] | [4] | 아직 구간 미완성 |
| 1·2 | 없음 | [0,1] | [4,2] | 미완성 |
| 2·3 | 뒤의 2(인덱스 1) | [0,2] | [4,3] | 4 |
| 3·1 | 앞의 0 만료 | [2,3] | [3,1] | 3 |
| 4·5 | 뒤의 3과 2 | [4] | [5] | 5 |
덱에서 빠진 값이 곧 창에서 사라졌다는 뜻은 아닙니다. 예제에서 위치 1의 값 2는 위치 2의 값 3이 들어올 때 덱에서 빠지지만, 창 [0,2] 안에는 여전히 있습니다. 다만 3이 2보다 크고 더 늦게 만료되므로 이후 이 창들의 최댓값에는 2가 다시 필요하지 않습니다. 이처럼 값으로 지배되어 버린 후보와 범위를 벗어나 만료된 후보를 서로 다른 이유로 제거합니다.
인덱스 경계와 입력 계약
windowMaximum(a, K):
require integer K and K >= 1
if K > length(a): return []
q = empty deque
answer = []
for i from 0 to length(a)-1:
while q not empty and q.front <= i-K:
q.pop_front()
while q not empty and a[q.back] <= a[i]:
q.pop_back()
q.push_back(i)
if i >= K-1:
answer.append(a[q.front])
return answer
이 계약은 K가 입력보다 크면 완성된 구간이 없으므로 빈 결과를 반환합니다. K=0은 잘못된 입력입니다. 실제 언어에서 i-K가 unsigned 언더플로를 만들지 않도록 타입을 선택하거나 i>=K인 경우에만 만료를 검사합니다.
동점에서 <=로 오래된 후보를 제거하면 같은 최댓값 중 최신 인덱스를 남깁니다. 값만 반환할 때는 결과가 같지만 가장 왼쪽 최댓값의 인덱스가 필요하면 <로 바꿔 동점 후보를 보존해야 합니다. 반환 계약이 비교 연산을 결정합니다.
구현을 점검할 때 [2, 2, 1], K=2를 넣으면 동점 제거 정책에 따라 첫 창의 최댓값 2 자체는 같지만 덱에는 최신 동점 인덱스만 남습니다. 인덱스도 반환하는 API라면 이 테스트의 기대 인덱스가 달라지므로 값 테스트만 통과해도 계약이 맞다고 볼 수 없습니다.
전체 비용과 개별 처리 지연
각 인덱스는 한 번 들어가고 앞 또는 뒤에서 최대 한 번 제거됩니다. 따라서 전체 시간 O(n), 덱의 보조 공간 O(K)입니다. 반환 배열은 O(n-K+1)이며 스트리밍 출력이면 따로 모으지 않을 수 있습니다.
한 단계에서 많은 뒤 후보를 지울 수 있어 개별 처리 지연이 항상 상수는 아닙니다. 그러나 전체 제거 횟수는 제한됩니다. 힙으로도 만료 항목을 지연 삭제할 수 있지만 관리 비용과 무효 항목 공간이 달라집니다. 이미 순서대로 들어오는 고정 길이 최댓값 문제에서는 덱의 제거 증명이 더 직접적입니다.
구간 의미 변경과 폐기 후보 복구 한계
K를 나중에 크게 늘리면 이미 만료시켜 버린 옛 값이 다시 범위에 들어갈 수 있습니다. 이 알고리즘이 그대로 복구해 주지 않습니다. 늦게 도착한 이벤트를 발생 시각으로 끼워 넣는 event-time 윈도도 입력 인덱스 순서의 고정 구간과 다릅니다.
검사는 모든 짧은 배열과 K에 대해 직접 max(a[l:l+K])를 계산한 결과와 비교하면 됩니다. 동일값·감소열·K=1·K=n·K>n을 포함하고, 매 단계 덱 인덱스가 증가하며 모두 현재 구간 안에 있는지 확인합니다. 단조성뿐 아니라 삭제한 후보가 다시 필요하지 않다는 시간 방향의 전제까지 지켜야 합니다.