Monotonic Deque 도입을 통한 Sliding Window Maximum 시간 복잡도 O(N·K)에서 O(N)으로 최적화

Context

고정 크기의 윈도우 내 최댓값을 탐색하는 과정에서 모든 요소를 반복 스캔하는 Brute Force 방식 사용. 윈도우 이동 시 중복 계산이 발생하여 입력 크기 N과 윈도우 크기 K에 비례하는 O(N × K)의 비효율적인 시간 복잡도 노출.

Technical Solution

• 불필요한 후보군 제거를 위한 Monotonic Deque 구조 설계
• 윈도우 범위를 벗어난 인덱스를 Deque 전면에서 제거하는 Window Boundary 관리
• 신규 요소 진입 시 해당 값보다 작은 기존 요소를 Deque 후면에서 모두 제거하여 내림차순 상태 유지
• 항상 Deque의 Front에 현재 윈도우의 최댓값이 위치하도록 보장하는 Candidate Filtering 로직 구현
• 모든 요소의 삽입과 삭제가 최대 1회로 제한되는 선형 시간 처리 구조 채택