贪心
做好优化，否者超时
对于第一位a,它只可能替换成a-1，所以如果在a到a-1的数字内只有a或者a-2，那么a-1就可以取代a。
因此我们可以开10个数组来存储每个数字的下标，对于每一位从0开始贪心的枚举每一位，如果有满足的j，那么直接替换，肯定有一个j满足要求（因为它自己肯定满足）。
代码里有一定的注释
点击查看代码
#include<bits/stdc++.h>
using namespace std;
vector<int> v[10];//一定要放在外面，不然会超时
void solve(){
string s;
cin>>s;
int n=s.length();
for(int i=n-1;i>=0;i--){
v[s[i]-'0'].emplace_back(i);//记录每个数字出现的位置，倒序是为了快速找到第一次出现的位置
}
for(int i=0;i<n;i++){//枚举每一位
for(int j=0;j<=9;j++){//从最小开始枚举
if(v[j].empty()) continue;
int flag=1;
for(int k=0;k<=9;k++){
if(abs(j-k)>1&&abs(j-k)<9&&!v[k].empty()&&v[k].back()<v[j].back()){
//不满足退出，枚举下一个j
//如果相差大于1或者不是9，肯定不满足，当然要确保它是否在其前面，或者它是否存在
flag=0;
break;
}
}
if(flag){
v[j].pop_back();
cout<<(char)(j+'0');
break;
}
}
}
cout<<'\n';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//取消同步不然会超时
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}