고정 크기 윈도 합

많은 문제에서는 k개의 연속된 요소로 이루어진 모든 블록의 합을 구하라고 합니다. 각 블록을 처음부터 다시 계산하는 것은 비효율적이므로 더 나은 방법을 사용할 수 있습니다. 🪟

순진한 방법은 길이가 k인 각 윈도의 합을 따로 구하는 것입니다. 이 방법은 작업을 반복하며 O(n × k)의 비용이 들어 큰 입력에서는 너무 느립니다.

서로 이웃한 윈도는 거의 완전히 겹칩니다. 한 칸 오른쪽으로 이동할 때는 가장 왼쪽 요소 하나를 제거하고 오른쪽에 새 요소 하나를 더하기만 하면 됩니다.

먼저 처음 k개 요소의 합을 한 번 구합니다. 이 하나의 합을 윈도가 앞으로 이동할 때마다 계속 갱신하면 됩니다.

윈도를 이동하려면 들어오는 요소를 더하고 나가는 요소를 뺍니다. 그러면 각 단계의 작업량을 일정한 O(1)로 유지할 수 있습니다.

각 이동이 끝날 때마다 지금까지 본 윈도 합의 최댓값처럼 필요한 값을 갱신합니다. 윈도의 값은 항상 즉시 사용할 수 있습니다.

각 요소를 더할 때 한 번, 제거할 때 한 번 더 확인하므로 전체 탐색은 O(n)입니다. 따라서 큰 제한도 쉽게 통과할 수 있습니다.

윈도에서 나가는 요소는 a[i - k]이지 a[i - 1]이 아닙니다. 이 오프셋을 올바르게 처리하지 못하는 것이 고정 윈도에서 가장 흔한 오류입니다.

합이 아니라 윈도의 평균을 최댓값으로 구해야 하나요? 추적 중인 윈도 합을 k로 나누기만 하면 됩니다. 슬라이딩 로직은 전혀 바뀌지 않습니다.

배열의 길이가 k보다 짧으면 완전한 윈도가 존재하지 않습니다. 처음에 len(a)와 k를 비교하고 일찍 반환하여 인덱스 오류를 피하십시오.

윈도의 길이가 고정되어 있고 합, 개수 또는 간단한 누적 통계처럼 값을 효율적으로 결합할 때 이 패턴을 사용하십시오.

배열을 가로질러 크기가 k인 윈도를 한 칸씩 오른쪽으로 이동합니다.

첫 번째 윈도를 한 번 초기화한 다음 각 단계에서 더하고 빼면서 O(1)에 이동하십시오. 전체 고정 크기 탐색은 선형 시간에 실행됩니다. ✅