알고리즘에서 '모노톤 스택(Monotone Stack)'이란 무엇인가요?

해설

모노톤 스택은 새 원소를 넣을 때 단조성(증가/감소)을 위반하는 기존 원소를 팝하여 항상 순서를 유지합니다. 이를 통해 각 원소의 '다음 큰 수(NGE)', '이전 작은 수', 히스토그램 최대 넓이 등의 문제를 한 번의 순회(O(n))로 해결할 수 있습니다.