Algorithm-cpp/baekjoon17298.cpp at master · bbeomgeun/Algorithm-cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <stack>
#define MAX 1000001
using namespace std;

typedef pair<int, int> pii;
int n, num, arr[MAX], record[MAX];
stack<pii> st;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		record[i] = -1;
	}

	for (int i = 0; i < n -1; i++) {
		if (arr[i] < arr[i + 1]) {
			record[i] = arr[i + 1];
			while (!st.empty()) {
				if (st.top().first < arr[i + 1]) {
					record[st.top().second] = arr[i + 1];
					st.pop();
				}
				else
					break;
			}
		}
		else {
			st.push(make_pair(arr[i], i));
		}
	}

	for (int i = 0; i < n; i++)
		cout << record[i] << " ";

}

//#include <iostream>
//#include <stack>
//#define MAX 1000001
//using namespace std;
//
//typedef pair<int, int> pii;
//int n, num, arr[MAX];
//stack<int> st;
//
//int main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cin >> n;
//	for (int i = 0; i < n; i++) {
//		cin >> arr[i];
//	}
//
//	for (int i = n - 1; i >= 0; i--) {
//		int a = arr[i];
//		while (!st.empty() && st.top() <= arr[i]) {
//			st.pop();
//		}
//		if (st.empty()) {
//			arr[i] = -1;
//		}
//		else {
//			arr[i] = st.top();
//		}
//		st.push(a);
//	}
//
//	for (int i = 0; i < n; i++)
//		cout << arr[i] << " ";
//}