Find Maximum in Sliding Window

설명

정수의 배열과 사이즈 w 의 Window 가 주어졌을 경우, Window (배열의 일부)가 배열 전체를 슬라이드 할 때 Window 중의 현재의 최대치를 찾습니다.

예

Window 의 Size 가 3 으로, 슬라이딩 해 가는 중에서, 모든 최대치를 찾아 봅시다.

step1

Window의 세 가지 요소 중 최대 값이 2

step2

하나의 시프트로 Window의 세 가지 요소 중 최대 값이 3

step3

하나의 시프트로 Window의 세 가지 요소 중 최대 값이 6


최종적으로 2　3　6　이 들어간 데이터 구조를 돌려주면 된다.

Solution

Time Complexity: O(n)

모든 요소는 한 번의 스캔으로 한 번만 deque에서 푸시되고 팝됩니다. 푸시와 팝은 O(1)이므로,
알고리즘은 Time Complexity O(n)에서 작동합니다.

Space Complexity: O(w)

Window의 사이즈분의 리스트를 사용하므로 Space Complexity 는 O(w)입니다.

거친 알고리즘의 흐름

이 알고리즘은 deque 데이터 구조를 사용하여 창에서 최대값을 찾습니다.
이 데이터 구조를 사용하는 목적은, 양단에 대해서, 데이터를 추가, 삭제라고 하는 푸시 및 팝 조작이 거의,
O(1)에서 기능하는 양단 큐이기 때문입니다. 이것이 창으로 작동합니다. 여기서 주의가 두 가지.
1. deque에 넣는 것은 배열의 요소가 아니라 요소의 Index.
2. deque의 선두에 최대치의 Index를, 말미에 그 이외의 Index를 넣어 간다.

알고리즘의 개시시에는, deque는 까다롭기 때문에, 최초의 윈도우 사이즈의 분만큼 요소의 Index를 추가해 간다.

추가하는 요소가 deque 뒤의 요소보다 작 으면 추가 된 요소는 새로운 deque의 끝 요소가됩니다.
만약, 추가하는 요소가 큰 경우는, 더 큰 요소가 발견될 때까지 deque 뒤측으로부터 반복 요소를 팝 해 가,
새로 끝으로 추가할 요소를 푸시합니다.

보시다시피, deque는 요소를 내림차순으로 저장합니다.
deque의 시작 부분에는 특정 창의 최대 값 인덱스가 포함됩니다.

창이 오른쪽으로 이동할 때마다 다음 단계를 반복합니다.

만약 deque 뒤의 요소가 현재 추가하는 요소보다 작거나 같으면 추가하는 요소보다 큰 요소의 인덱스가 나올 때까지 요소를 deque에서 삭제합니다.

하나의 윈도우를 어긋나면, 값이 현재의 윈도우에 들어가지 않게 되는 경우에, 선두의 요소 인덱스를 삭제합니다.

창 뒤에 현재 요소의 인덱스를 푸시합니다.

코드