在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, ]