단조 스택
오른쪽 후보를 기다리며 값과 인덱스를 함께 보존한다.
문제 신호가 단조 스택·큐 선택을 결정한다
후보가 한 번 밀려나면 다시 답이 될 수 없을 때 단조 구조를 쓴다. 남겨야 하는 정보는 문제의 답 형태가 정한다.
단조 큐
창 밖 후보를 먼저 제거하고 뒤에서 약한 후보를 버린다.
인덱스 필수
값만 저장하면 거리와 만료 판단을 복원할 수 없다.
구조Stack
저장index, value
불변식새 값보다 작은 후보만 pop
실패답이 중복 기록됨
구조Deque
저장index, value
불변식front 만료 제거 후 back 약한 후보 pop
실패창 밖 값이 최댓값으로 남음
구조Stack
저장index, price
불변식하락할 때만 기간 확정
실패같은 가격에서 기간이 끊김
판정 순서: 후보가 다시 살아날 수 없는가 → 값만으로 충분한가 → 창 만료가 필요한가.