🌉 Monotonic Stack

intro

🌉 stack의 (파이썬 코드 기준 append()와 pop()) 연산이 O(1)임을 감안해 한 곳에서 넣고 빼고를 반복하는 과정에서 stack의 원소가 오름차순 또는 내림차순을 유지하게끔 하는 stack을 만드는 유형을 'monotonic stack' 유형이라고 한다.

 

🌉 아래 예시와 같이 내림차순으로 이루어진 stack을 유지하면서, 새로운 원소 6이 들어올 때 pop() 연산 4번 진행 후 빠르게 append() 진행

🌉 오름차순 또는 내림차순 순서 stack으로 업데이트 되는 과정에서 현재 원소보다 오른쪽 또는 왼쪽 원소 중 가장 가까이 있는 원소 최대/최솟값 구하기 또는 현재 원소보다 오른쪽 또는 왼쪽 원소 중 가장 가까이 있는 원소의 위치 구하기가 대표 유형으로 많이 나온다.

 

🌉 예시 코드(오름차순을 유지한 상태에서 13을 넣어 stack update)

stack = [3, 5, 9, 12, 15]
x = 13
while stack:
    if stack[-1] >= x:
        stack.pop()
    else:
        stack.append(x)
        break
print(stack) #[3, 5, 9, 12, 13]

Exercises

★ <BOJ G3 17299 오등큰수>

: 현재 원소보다 오른쪽에 있으면서 등장 횟수가 큰 수 중 가장 왼쪽에 있는 수 출력. 등장 횟수는 별도로 Counter 활용

 

★ <BOJ G4 17298 오큰수>

: 17299와 동일한 문제. 다만 등장 횟수가 아닌 단순히 큰 수 중 가장 왼쪽에 있는 수 출력

 

★ <BOJ G5 2493 탑>

: 현재 원소보다 왼쪽에 있으면서 자신보다 큰 원소 중 가장 가까운 원소 위치 출력

 

★ <BOJ G5 6198 옥장 정원 꾸미기>

: 현재 원소보다 오른쪽에 있으면서 자신보다 큰 원소의 개수를 누적으로 합해서 출력

 

★ <BOJ G5 21956 Treasure>

: monotonic stack의 내부 update 과정을 문제로 그대로 표현

 

★ <BOJ G5 24305 ОТЧЕТ>

: 현재 원소보다 오른쪽에 있으면서 자신보다 큰 수 중 가장 왼쪽에 있는 수 출력