class Solution {
public:
struct stringnode{
int cmpnum;
int order;
stringnode():cmpnum(0),order(0){}
};
static bool cmp(stringnode a,stringnode b){
if(a.cmpnum!=b.cmpnum) return a.cmpnum<b.cmpnum;
else return a.order<b.order;
}
vector<int> diStringMatch(string s) {
int len=s.length()+1;
vector<stringnode> S(len);
for(int i=0;i<len-1;++i){ //D说明后一个数比较小，I说明后一个数比较大
if(s[i]=='I') S[i+1].cmpnum=S[i].cmpnum+1;
else S[i+1].cmpnum=S[i].cmpnum-1;
S[i+1].order=i+1;
}
sort(S.begin(),S.end(),cmp);
for(int i=0;i<len;++i)
S[i].cmpnum=i;
vector<int>ans(len,0);
for(int i=0;i<len;++i)
ans[S[i].order]=S[i].cmpnum;
return ans;
}
};
贪心：
class Solution {
public:
vector<int> diStringMatch(string s) {
vector<int> result;
int min = 0, max = s.size();
for(auto& str:s) {
if(str == 'I') result.emplace_back(min++); /* 遇到‘I’找到剩余数中的最小值放入resul中 */
else result.emplace_back(max--); /* 遇到‘D’找到剩余数中的最大值放入resul中 */
}
result.emplace_back(max); //最后一个值max=min
return result;
}
};
