동점이 붙은 작은 입력
`[2,2,3]`, `[1,3,3,2]`, `[3,3,2]`처럼 같은 값이 연속된 배열을 먼저 실행합니다.
동점 처리 연산자 하나가 단조 불변식을 바꾼다
다음 큰 수, 윈도우 최댓값, 주식 가격 지속 기간은 모두 후보를 버리는 구조지만 동등한 값에서 남길 인덱스가 서로 다릅니다.
다음 큰 수
`nums[top] < x`
strict greater
같은 값은 답이 아니므로 스택에 남깁니다.
`[2,2,3]`에서는 두 2가 모두 3을 만나야 확정됩니다.
윈도우 최댓값
`nums[back] <= x`
newer duplicate
같은 최댓값이면 더 오래 살아남는 뒤쪽 인덱스를 남깁니다.
범위 밖 제거 후에도 최신 동점 후보가 답을 이어받습니다.
주식 가격 지속 기간
`price[top] > x`
drop only
가격이 같으면 하락이 아니므로 아직 기간이 끝나지 않습니다.
`[3,3,2]`에서 두 3은 2를 만났을 때 각각 종료됩니다.
push와 pop 횟수 비교
각 인덱스가 한 번 들어오고 한 번만 나가는지 보면 `O(N)` 근거도 같이 확인됩니다.
문제의 “크다” 정의
“큰 값”인지 “크거나 같은 값”인지 문장을 먼저 표시해야 조건식이 흔들리지 않습니다.
단조 구조를 고를 때는 자료구조보다 비교 연산자가 먼저입니다. 동점 반례를 통과하면 후보 제거 조건과 윈도우 범위 처리가 함께 안정됩니다.