Monotone Stack, Monotone Queue (단조 스택, 단조 큐)

1. Monotone Stack (단조 스택)

- 스택의 원소들을 단조롭게(오름차순 or 내림차순) 유지하는 기법이다.

 

 

그림으로 Monotone Stack 이해하기

- 아래 그림과 같은 수열이 있을 때, 오름차순으로 단조 스택을 만드는 과정은 다음과 같다.

 

구현 방법

수열을 순회하면서 다음을 수행한다.

• pop
  top의 원소를 확인해서 현재 값보다 크거나 같은 값들을 제거한다. (오름차순)
• push
  현재 값을 스택에 저장한다.

 

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
typedef long long ll;
using namespace std;

int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);

	int n;
	ll tmp, ans = 0;
	stack<ll> st;

	cin >> n;
    
	for (int i = 0; i < n; i++) {
		cin >> tmp;

		while (!st.empty() && (st.top() <= tmp))
			st.pop();
            
		ans += st.size();
		st.push(tmp);
	}
    
	cout << ans;
	return 0;
}

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

 

2. Monotone Queue (단조 큐)

- 큐 안의 원소들을 단조롭게(오름차순  or  내림차순) 유지하는 기법이다.

 

 

그림으로 Monotone Queue 이해하기

- 아래 그림과 같은 수열이 있을 때, 오름차순으로 단조 큐를 만드는 과정은 다음과 같다.

 

구현 방법

수열을 순회하면서 다음을 수행한다.

• pop_back
  뒤에서부터 현재 값보다 크거나 같은 값들을 제거한다. (오름차순)
• push_back
  현재 값을 큐의 맨뒤에 저장한다.
• pop_front
  조건에 만족하지 않는 수들을 앞에서부터 제거한다.

 

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
typedef long long ll;
using namespace std;

int main() {
    ll n, m, tmp;
    deque<pair<ll, ll>> dq;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> tmp;

        while (!dq.empty() && tmp <= dq.back().first)
            dq.pop_back();

        dq.push_back({ tmp,i });

        while (dq.front().second <= i - m)
            dq.pop_front();

        cout << dq.front().first << ' ';
    }
}

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

+) 모노톤 큐는 슬라이딩 윈도우 알고리즘에서 min / max 값을 찾기에 용이하다.