MONOTONIC

후보 집합을 작게 유지해야 단조 구조가 된다

새 값이 들어올 때마다 만료된 후보와 지배당한 후보를 제거하고, 살아남은 인덱스만 다음 답 후보로 남긴다.

예시: 다음 큰 수에서 3을 읽는 순간

before
2 1 top new 3
while
1 pop 2 pop answer = 3
after
3 top push once

스택과 큐에서 같은 질문

stack

뒤쪽 후보 제거

새 값이 top을 이기면 top은 답이 확정되어 나간다.

queue

앞쪽 만료 제거

윈도우 왼쪽을 벗어난 후보는 비교 전에 먼저 빠진다.

proof

한 번씩만 이동

각 인덱스가 push 1회, pop 1회라 전체가 O(N)이다.

1. 범위 확인 창 밖 인덱스를 먼저 버린다.
2. 지배 확인 새 값이 이기는 후보를 뒤에서 제거한다.
3. 후보 추가 남은 순서를 깨지 않게 새 인덱스를 넣는다.

A등급 기준 핵심: 독자는 선 없이도 “왜 버려도 되는가”와 “왜 O(N)인가”를 후보 변화만 보고 읽을 수 있어야 한다.