길이 K의 이동 구간 최댓값을 매번 정렬하지 않고 구하려 합니다. deque에는 무엇을 남기나요?

현재 구간에서 최댓값 후보가 될 수 있는 인덱스를 값의 단조 순서로 유지합니다. 새 값보다 작아 앞으로 최댓값이 될 수 없는 뒤 후보를 제거하고 구간 밖의 앞 인덱스를 제거합니다.

동작 원리와 전제

deque 앞이 현재 최댓값을 가리킵니다. 값만 보관하면 같은 값의 만료 시점을 구분하기 어려워 인덱스를 사용합니다. 같은 값 처리에서 오래된 후보를 남길지 새 후보로 바꿀지 일관된 비교 규칙을 정합니다.

선택과 실패 처리

각 인덱스가 한 번 들어가고 한 번 제거되어 전체 O(n)을 얻을 수 있습니다. K가 0·입력보다 큰 경우 결과 계약을 정하고 메모리는 구간 크기에 제한합니다. 구간 합·중앙값은 다른 구조가 필요합니다.

구체적인 사례와 검증

입력 [4,2,3]에서 새 3이 들어오면 뒤의 2는 앞으로 같은 구간에 남는 동안 3보다 유리할 수 없어 제거할 수 있습니다. 하지만 4는 더 커서 유지하고 구간 밖으로 나갈 때만 앞에서 제거합니다. 이 논리 때문에 값의 크기뿐 아니라 인덱스의 시간 순서를 함께 저장합니다. K가 바뀌는 동적 요구는 기존 알고리즘의 가정을 바꿀 수 있어 그대로 재사용하지 않습니다. 스트림에서 늦은 데이터가 들어오는 경우도 단순 입력 순서 윈도와 event-time 윈도가 다릅니다. 자료구조가 표현하는 구간의 정의를 먼저 정하고 그 조건에서 후보 제거가 안전한지 검증합니다.

동일값·단조 입력·K=1·전체 구간·경계 만료를 기준 구현과 비교합니다. 새 항목 처리와 오래된 항목 제거 순서가 실제 구간 정의와 맞는지 검사합니다. 단순히 deque를 썼다는 사실보다 후보를 버려도 안전한 이유가 핵심입니다.