[Algorithm] monotone stack 알고리즘

monotone stack이란 단조로운 스택이란 뜻입니다.

 

단조로운 스택이란 무슨 말이냐면 항상 오름차순 또는 내림차순이 유지되는 스택을 의미합니다.

 

스택의 원소들을 O(n)시간복잡도를 가지면서 중복을 허용하지 않고 오름차순 또는 내림차순 상태를 유지하게 합니다.

 

stack의 top에 있는 원소들을 새롭게 들어오려는 원소와 비교하여, 경우에 따라 pop을 진행합니다.

 

1. 중복없는 오름차순 stack의 경우, 들어오려는 원소가 stack의 top보다 작거나 같은경우 오름차순을 만족할떄까지 pop을 반복한 후 원소를 삽입해주어 오름차순을 유지합니다.

2. 중복없는 내림차순 stack의 경우, 들어오려는 원소가 stack의 top보다 크거나 같은경우 내림차순을 만족할때까지 pop을 반복한 후 원소를 삽입해주어 내림차순을 유지합니다.

 

아래와 같은 숫자들을 monotone stack으로 오름차순 유지로 과정을 보여보겠습니다.

 

5 19 46 20 10 16 18 15 15 29 47 20

 

맨 처음 stack에 아무것도 없으면 원소를 삽입합니다.

5

 

49까지는 계속 넣어줍니다.

5 19 46

 

20을 넣어야 하는데 오름차순을 유지해야 하므로 오름차순을 유지할 수 있을때까지 원소를 pop해줍니다.

5 19

 

그 후 20을 삽입합니다.

5 19 20

 

다음 원소는 10입니다. 이번에도 오름차순을 만족할때까지 pop을 수행합니다.

5

 

그리고 원소를 삽입합니다.

5 10

 

18까지 오름차순을 만족하므로 계속 넣어줍니다.

5 10 16 18

 

15가 다음 원소입니다. 오름차순을 만족하기 위해 pop을 진행합니다.

5 10

 

원소 15를 삽입해줍니다.

5 10 15

 

다음 원소도 15입니다. 오름차순을 만족할떄까지 pop해줍니다.

5 10

 

그리고 원소 15를 삽입합니다.

5 10 15

 

47까지 오름차순이므로 삽입합니다.

5 10 15 29 47

 

20을 넣기위해 오름차순 정렬하기위해 pop해줍니다.

5 10 15

 

원소 20을 삽입해줍니다.

5 10 15 20

 

이렇게 오름차순 상태를 유지하면서 모든 원소를 넣었습니다.

 

monotone stack 오름차순을 파이썬 코드로 표현하면 이렇게 됩니다.

while stack and stack[-1] >= arr[i]:
    stack.pop()
stack.append(arr[i])

 

 

참고한 블로그 : 

https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/