阅读量:1
题目描述
给定一个长度为𝑛n的、仅由小写字母组成的字符串，将其按序依次放入栈中。
请问在所有可能的出栈序列中，字典序最小的出栈序列是多少？
输入格式
输入第一行， 一个正整数𝑛n
输入第二行，一个长度为𝑛n的字符串
输出格式
输出所有出栈序列中，字典序最小的出栈序列
数据范围
- 对于30%30%的数据，1≤𝑛≤101≤n≤10
- 对于60%60%的数据，1≤𝑛≤1031≤n≤103
- 对于100%100%的数据，1≤𝑛≤1051≤n≤105
样例数据
输入:
3
yes
输出:
esy
说明:
字符y、e、s依次进栈，所有出栈的可能性有：
{yes}、{yse}、{eys}、{esy}、{sey}
其中 {esy} 的字典序最小
详见代码:
#include <bits/stdc++.h> using namespace std; string a; char b[100005]; string ans = ""; stack<char> s; int n; int main() { cin >> n; cin >> a; b[n]='z'; for (int i = n - 1; i >= 0; i--) { b[i] = min(b[i+1],a[i]); } for (int i = 0; i < n; i++) { while(!s.empty() && s.top() <= b[i]) { ans += s.top(); s.pop(); } if (a[i] == b[i]) { ans += a[i]; } else { s.push(a[i]); } } while (!s.empty()) { ans += s.top(); s.pop(); } cout << ans; return 0; }