[Stack] Monotonic Stack (단조 스택 )

[2021.12.20] 글 작성

💡 이론

1. 목적

   기본적인 스택 기능을 가지며 모든 원소들이 오름차순(혹은 내림차순)을 유지하도록 한다.

2. 과정

Ex) 2, 7, 6, 3, 5, 9을 Monotonic Stack에 넣을 때 (오름차순)
[2] -> [2, 7] -> [2, 6] (pop 7)  -> [2, 3] (pop 6) -> [2, 3, 5] -> [2, 3, 5, 9]

3. 코드

#include <iostream>
#include <stack>

using namespace std;

stack<int> mono_stack;

int arr[6] = { 2, 7, 6, 3, 5, 9 };

int main() {
    for(int i = 0; i < 6; i++) {
        while(!mono_stack.empty() && mono_stack.top() > arr[i]){
          mono_stack.pop();
        }
        mono_stack.push(arr[i]);
    }
    while(!mono_stack.empty()){
      cout << mono_stack.top() << ' ';
      mono_stack.pop();
    }
    cout << '\n';
    return 0;
}

4. 결과

   

Ref.
Special Data Structure: Monotonic Stack
monotone stack
Algorithms for Interview 2: Monotonic Stack