monotone stack

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

17298번: 오큰수

 

-- 처음에 문제를 접근 했을때 bruth-force 로 문제를 접근 하였다.

 

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>

using namespace std;
int main() {

	std::ios::sync_with_stdio(false); cin.tie(0);

	int n; cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int prev = arr[0];

	for (int i = 0; i < n; i++) {
		int cand = arr[i];
		
		bool find = false;
		int find_n = -1;
		for (int j = i + 1; j < n; j++) {
			if (cand < arr[j]) {
				find = true;
				find_n = arr[j];
				break;
			}
		}

		cout << find_n << " ";
	}

	return 0;
}

역시나 쉬운 문제는 아니 였으며 시간 초과가 나왔다.

 

해당 문제를 접근 하기 위해서 단순  bruth-force 가 아닌 방법이 필요 한걸로 파악됬다.

 

인터넷이랑 기타 백준 강의를 들으면서 힌트를 얻은 거이

 

"monotone stack" 이라는 방법을 사용 하면 된다고 한다.

 

1. 배역의 맨 뒤부터 스택에 넣고, 스택을 항상 순감소 상태로 유지한다.

2. 계산을 해보면 스택의 맨 위에 있는 원소가 Ai의 오른쪽에 있으면서 Ai보다 큰 수 중 가장 왼쪽에 있는 수가 된다.

3. 처음에 stack 에 값에 -1을 처리해주는 것은 처음에 스택에  INF 를 넣은다.

 

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>

using namespace std;
int main() {

	std::ios::sync_with_stdio(false); cin.tie(0);

	int n; cin >> n;
	vector<int> v(n), ans(n);
	for (int i = 0; i < n; i++) cin >> v[i];

	stack<int> stk; stk.push(1e9 + 7);
	for (int i = n - 1; i >= 0; i--) {
		while (stk.top() <= v[i]) {
			stk.pop();
		}
		if (stk.top() >= 1e9) {
			ans[i] = -1;
		}
		else {
			ans[i] = stk.top();
		}

		stk.push(v[i]);
	}
	for (auto i : ans) cout << i << " ";

	return 0;
}