在C ++中查找排列
假设我们有一个由字符“D”和“I”组成的秘密签名。“D”表示两个数字之间的递减关系，“I”表示两个数字之间的递减关系。秘密签名由一个特殊的整数数组构造而成，该数组唯一包含从1到n的所有不同数字。
例如，秘密签名“DI”可以由类似[2,1,3]或[3,1,2]的数组构造，但不能使用类似[3,2,4]或[2，1,3,4]，它们都是非法构造不能代表“DI”秘密签名的特殊字符串。
现在我们必须找到[1，2，...n]在字典上最小的排列，该排列可以引用输入中的给定秘密签名。
因此，如果输入类似于“DI”，则输出将为[2,1,3]。众所周知，[3,1,2]也可以构造秘密签名“DI”，但是由于我们要查找词典排列最小的那个，我们需要输出[2,1,3]
为了解决这个问题，我们将遵循以下步骤-
定义一个堆栈st
中位数：=2
定义数组ret
对于初始化i：=1，当i<=s的大小时，更新（将i增加1），-
在ret结尾处插入i
虽然（不是st为空），请-
在ret的末尾插入st的top元素
从st删除元素
将我插入st
如果s[i-1]与'D'相同，则-
除此以外
将s的大小插入st
虽然（不是st为空），请-
在ret的末尾插入st的top元素
从st删除元素
返回ret
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int< findPermutation(string s) {
stack <int< st;
int cnt = 2;
vector <int< ret;
for(int i = 1; i <= s.size(); i++){
if(s[i - 1] == 'D'){
st.push(i);
}
else{
ret.push_back(i);
while(!st.empty()){
ret.push_back(st.top());
st.pop();
}
}
}
st.push(s.size() + 1);
while(!st.empty()){
ret.push_back(st.top());
st.pop();
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.findPermutation("DIID"));
}输入值
"DIID"
输出结果
[2, 1, 3, 5, 4, ]