정의

단조 스택은 원소(보통 인덱스)가 항상 증가 또는 감소 순서를 유지하도록 관리되는 스택입니다. '다음 큰 원소' 문제에서는 스택에 인덱스를 쌓되, 스택에 담긴 값들이 위로 갈수록 작아지는(단조 감소) 상태를 유지합니다.

핵심 특성

• ✓값이 아니라 '인덱스'를 스택에 저장 - 나중에 답을 어느 위치에 채울지 알기 위함
• ✓스택 맨 위 값보다 큰 새 값이 오면 pop하며 답을 채움 - 그 원소의 다음 큰 원소를 찾은 것
• ✓각 인덱스는 정확히 한 번 push되고 최대 한 번 pop됨 - 그래서 전체 O(n)
• ✓끝까지 pop되지 않고 남은 인덱스는 다음 큰 원소가 없음 - 답은 -1

시간 복잡도