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

Leetcode에 단골로 등장하는 인터뷰 질문 Monotonic Stack에 대해서 알아보겠습니다.

Monotnic 영어 단어에서 알수 있듯, 단조 증가/ 단조 감소순으로 stack을 쌓아가며 값을 구해가는 데이터 구조인데요

 

예제를 통해 핵심 개념을간단히 먼저 보겠습니다.

 [6,5,4,7,8] 을 활용해 단조 감소 (Monotonic-decreasing) 스택을 쌓는다고 할 때,

6 >5 >4 ==> 리스트를 순회하며 stack에 쌓습니다

7 -> 8 ===> 값이 증가하기 때문에 stack에 쌓지 않고 pop합니다

 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

우리가 알고 있는 stack 의 개념과 동일하지만, stack의 push와 pop을 진행하는 때가 요소들의 단조 증가/감소 여부에 달려있는 것이죠. 이렇게 단조 증가/감소에 맞지 않는 요소들을 pop해내가며 전체를 순회하기 때문에 Monotonic Stack은 O(n) 시간 복잡도를 가집니다. 주어진 인풋 배열을 반복적으로 순회하는 것이 아니기 때문에 시간 효율성이 높은 편입니다

 

 

Geeks for geeks 의 코드를 통해 단조 증가 stack을 쌓아보겠습니다.

 

Q. [1,4,5,3,12,10]의 배열이 있을 때, 단조증가 STACK을 구하시오

 

def Increasing_MonoStack(arr):
	stac = []
	for i in range(len(arr)):
		while len(stac) > 0 and stac[len(stac)-1] > arr[i]: # 스택에 들어가있는 값보다 작은 값이 나올때 (값이 감소할 때)
			stac.pop() # 값을 pop한다
		stac.append(arr[i])
        
     #스택에 쌓아놓은 요소들을 ans라는 리스트에 담는 과정
     ans = [0]*len(stac)
     j = len(stac) -1
     
     while(len(stack) != 0):
     	ans[j] = stac[len(stac)-1] #stack은 LIFO 구조이기 때문에 뒤에서 부터 채워줍니다
        stac.pop()
        j -= 1

 

이 코드가 Monotonic stack의 템플릿은 아니지만,

1) for 문을 통해 전체 배열을 돌면서 

2) 스택의 마지막 값(가장 최근에 push한 값)과 비교해서 증가/감소에 맞지 않는 값을 while문으로 걸러서 pop 하고

3) 그 외의 경우를 append하는 형태는 여러 문제에서 공통적으로 나오는 개념적 구조인 것 같습니다.

 

 

관련 Leetcode 문제들 ↓

https://leetcode.com/problems/trapping-rain-water/

https://leetcode.com/problems/largest-rectangle-in-histogram/

 

 

 

참고 자료:

https://www.geeksforgeeks.org/introduction-to-monotonic-stack/

https://medium.com/techtofreedom/algorithms-for-interview-2-monotonic-stack-462251689da8

https://levelup.gitconnected.com/what-is-a-monotonic-stack-f10d79609c45