Monotonic Stack (단조 스택)
- Monotonic Stack 을 알아보기 전에, 먼저 스택이 무엇인지 간단히 살펴보자.
스택 (stack) : LIFO (Last In First Out) 의 후입선출 형식으로 제일 마지막에 삽입된 원소가 가장 처음 나오는 알고리즘
- 이러한 스택의 원소들을 오름차순 또는 내림차순으로 정렬한다면, 배열에서 특정한 정보를 얻어 낼 수 있다.
- 주로 next greatest element finding 에 그 정보가 활용된다.
- 단조 스택 예시 (next greatest element finding)
배열 [7, 1, 9, 8, 15]
특정 원소의 오른쪽에 자신보다 큰 값이 있는지를 찾는 문제
스택은 내림차순으로 유지
1st step)
스택에 15 삽입 (top = 0)
스택에 15만 있으므로, index 배열 : [7]
2nd step)
스택의 top에 해당하는 값 15가 8보다 크므로, index 배열 : [4, 4]
스택에 8 삽입 (top = 1)
3rd step)
스택의 top에 해당하는 값 8이 9보다 작으므로, 9보다 큰 값이 나올 때까지 pop 수행
top = 0 에 해당하는 15가 9보다 크므로, index 배열 : [4, 4, 4]
스택에 9 삽입 (top = 1)
4th step)
스택의 top에 해당하는 값 9가 1보다 크므로, index 배열 :
[4, 4, 4, 2]
스택에 1 삽입 (top = 2)
5th step)
스택의 top에 해당하는 값 1이 7보다 작으므로, 7보다 큰 값이 나올 때까지 pop 수행
top = 1 에 해당하는 9가 7보다 크므로, index 배열 :
[4, 4, 4, 2, 2]
스택에 7 삽입 (top = 2)
스택 : [15, 9, 7]
index 배열 : [4, 4, 4, 2, 2]
-
위와 같이 내림차순 유지를 위한 push 와 pop 을 번갈아 가면서 수행하여 next greatest element 를 탐색
-
시간복잡도는 평균적으로 O(n) 이므로, 브루트포스 알고리즘보다 효율적이다.
