【题解】【上海】【出栈序列】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1E5 + 10; 
string s;
int n;
char a[MAXN]; 
int main(){
	cin >> n >> s;
	a[n - 1] = s[n - 1];
	for (int i = n - 2; i >= 0; --i)
		a[i] = min(s[i], a[i + 1]);//寻找字符串各个位置的最小子序列
	stack<char>stk;
	stk.push(s[0]);
	int inc = 1;
	while (!stk.empty() || inc < n){
		if (stk.empty() || inc < n && stk.top() > a[inc]){
			stk.push(s[inc++]);
		} else{
			cout << stk.top();
			stk.pop();
		}
	}
	cout << endl;
	return 0;	
}