Monotonic Stack 개념 정리 (Push하고 Pop하고)

Leetcode에 단골로 등장하는 인터뷰 질문 Monotonic Stack에 대해서 알아보겠습니다. Monotnic 영어 단어에서 알수 있듯, 단조 증가/ 단조 감소순으로 stack을 쌓아가며 값을 구해가는 데이터 구조인데요 예제를 통해 핵심 개념을간단히 먼저 보겠습니다. [6,5,4,7,8] 을 활용해 단조 감소 (Monotonic-decreasing) 스택을 쌓는다고 할 때, 6 >5 >4 ==> 리스트를 순회하며 stack에 쌓습니다 7 -> 8 ===> 값이 증가하기 때문에 stack에 쌓지 않고 pop합니다 우리가 알고 있는 stack 의 개념과 동일하지만, stack의 push와 pop을 진행하는 때가 요소들의 단조 증가/감소 여부에 달려있는 것이죠.

이렇게 단조 증가/감소에 맞지 않는 요소들.....