题解 | 交换到最大

t = int(input())

for _ in range(t):
    s = list(input())
    n = len(s)
#从第i未开始固定最有价值的值，任何距离当前位置超过 9 的字符，移动过来的价值都必然是负数
    for i in range(n):
        bst_val = int(s[i])#当前第i位最有价值的值
        bst_pos = i#当前第i位最有价值的值的坐标
        for j in range(i, min(i + 10, n)):#在滑动窗口内，寻找第i为最有价值的值，找到后记录
            cur_val = int(s[j]) - (j - i)
            if cur_val > bst_val:
                bst_val = cur_val
                bst_pos = j
        tmp_pos = bst_pos#找到了当前（i）位最有价值的值，要把这个值移动到第i位
        while tmp_pos > i:
            s[tmp_pos], s[tmp_pos - 1] = s[tmp_pos - 1], s[tmp_pos]
            tmp_pos -= 1
        s[i] = str(bst_val)
#输出交换完成后的数字
    print("".join(s))