Monotonic stack

monotonic stack은 요소가 단조 증가 또는 감소하는 스택이다.

단조 증가/감소하는 스택의 요소값 혹은 요소의 인덱스를 저장해야 할 때 사용한다.

현재 원소 x보다 왼쪽에 있는 원소 중에서 처음으로 나오는 x이하/이상의 수의 위치를 바로 알 수 있습니다.

참고

• https://liuzhenglaichn.gitbook.io/algorithm/monotonic-stack
• https://velog.io/@soopsaram/Monotonic-Stack-%EB%AC%B8%EC%A0%9C
• https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/