交换到最大

思路

操作的本质是：选一个非首位、非零的数字，减 1 后和左邻交换。反复操作就是把一个数字 $d$ 往左移 $k$ 步，代价是值减少 $k$ ，到达后变成 $d-k$ （需要 $d \ge k$ ）。

关键观察：数字最大是 9，所以任何数字最多只能左移 9 步。

这意味着对于结果的第 $i$ 位，候选人只来自剩余数字序列中的前 10 个元素。贪心策略很自然：

从左到右确定每一位
对当前位，查看剩余序列中前 10 个数字（偏移量 $k = 0, 1, \ldots, 9$ ）
选「到达值 $d - k$ 」最大的那个放到当前位
从序列中删掉被选中的数字

当一个数字被移到前面时，它经过的那些数字会自然右移一位，维持相对顺序不变——这和链表中"删除节点"的效果完全一致。

用链表维护剩余数字序列，每轮最多看 10 个节点，总时间 $\mathcal{O}(10n)$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    scanf("%d", &t);
    string ss;
    while(t--){
        ss.clear();
        int c;
        while((c = getchar()) != EOF && (c == '\n' || c == '\r' || c == ' '));
        if(c != EOF) ss.push_back(c);
        while((c = getchar()) != EOF && c >= '0' && c <= '9')
            ss.push_back(c);

        int n = ss.size();
        if(n == 0) continue;

        vector<int> dig(n), nxt(n+1), prv(n+1);
        for(int i = 0; i < n; i++){
            dig[i] = ss[i] - '0';
            nxt[i] = i + 1;
        }
        for(int i = 1; i <= n; i++) prv[i] = i - 1;
        prv[0] = -1;

        int head = 0;
        string result;
        result.resize(n);

        for(int pos = 0; pos < n; pos++){
            int bestVal = -1, bestNode = -1;
            int cur = head;
            for(int k = 0; k < 10 && cur < n; k++){
                int arrived = dig[cur] - k;
                if(arrived >= 0 && arrived > bestVal){
                    bestVal = arrived;
                    bestNode = cur;
                }
                cur = nxt[cur];
            }

            result[pos] = '0' + bestVal;

            int p = prv[bestNode], nx = nxt[bestNode];
            if(bestNode == head){
                head = nx;
                if(nx < n) prv[nx] = -1;
            } else {
                nxt[p] = nx;
                if(nx < n) prv[nx] = p;
            }
        }
        puts(result.c_str());
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            String s = br.readLine().trim();
            int n = s.length();
            int[] digits = new int[n];
            for (int i = 0; i < n; i++) digits[i] = s.charAt(i) - '0';

            int[] nxt = new int[n + 1];
            int[] prv = new int[n + 1];
            for (int i = 0; i < n; i++) {
                nxt[i] = i + 1;
                prv[i + 1] = i;
            }
            prv[0] = -1;
            int head = 0;

            char[] result = new char[n];
            for (int pos = 0; pos < n; pos++) {
                int bestVal = -1, bestNode = -1;
                int cur = head;
                for (int k = 0; k < 10 && cur < n; k++) {
                    int arrived = digits[cur] - k;
                    if (arrived >= 0 && arrived > bestVal) {
                        bestVal = arrived;
                        bestNode = cur;
                    }
                    cur = nxt[cur];
                }

                result[pos] = (char) ('0' + bestVal);

                int p = prv[bestNode];
                int nx = nxt[bestNode];
                if (bestNode == head) {
                    head = nx;
                    if (nx < n) prv[nx] = -1;
                } else {
                    nxt[p] = nx;
                    if (nx < n) prv[nx] = p;
                }
            }

            sb.append(new String(result)).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
out = []
for _ in range(t):
    s = input().strip()
    n = len(s)
    dig = [int(c) for c in s]
    nxt = list(range(1, n + 2))
    prv = list(range(-1, n))
    head = 0
    result = []

    for pos in range(n):
        bestVal = -1
        bestNode = -1
        cur = head
        for k in range(10):
            if cur >= n:
                break
            arrived = dig[cur] - k
            if arrived >= 0 and arrived > bestVal:
                bestVal = arrived
                bestNode = cur
            cur = nxt[cur]

        result.append(str(bestVal))

        p = prv[bestNode]
        nx = nxt[bestNode]
        if bestNode == head:
            head = nx
            if nx < n:
                prv[nx] = -1
        else:
            nxt[p] = nx
            if nx < n:
                prv[nx] = p

    out.append(''.join(result))

sys.stdout.write('\n'.join(out) + '\n')

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const t = parseInt(lines[0]);
    const res = [];
    for (let ti = 0; ti < t; ti++) {
        const s = lines[1 + ti].trim();
        const n = s.length;
        const dig = new Array(n);
        const nxt = new Array(n + 1);
        const prv = new Array(n + 1);
        for (let i = 0; i < n; i++) {
            dig[i] = s.charCodeAt(i) - 48;
            nxt[i] = i + 1;
        }
        for (let i = 1; i <= n; i++) prv[i] = i - 1;
        prv[0] = -1;
        let head = 0;
        const result = new Array(n);

        for (let pos = 0; pos < n; pos++) {
            let bestVal = -1, bestNode = -1;
            let cur = head;
            for (let k = 0; k < 10 && cur < n; k++) {
                const arrived = dig[cur] - k;
                if (arrived >= 0 && arrived > bestVal) {
                    bestVal = arrived;
                    bestNode = cur;
                }
                cur = nxt[cur];
            }
            result[pos] = String(bestVal);

            const p = prv[bestNode];
            const nx = nxt[bestNode];
            if (bestNode === head) {
                head = nx;
                if (nx < n) prv[nx] = -1;
            } else {
                nxt[p] = nx;
                if (nx < n) prv[nx] = p;
            }
        }
        res.push(result.join(''));
    }
    console.log(res.join('\n'));
});

复杂度

时间复杂度： $\mathcal{O}(n)$ ，其中 $n$ 是所有字符串总长度。每个位置最多检查 10 个候选。
空间复杂度： $\mathcal{O}(n)$ ，链表前驱后继数组。

总结

这道题的突破口在于意识到数字 0–9 的值域很小，所以每个数字最多只能往左移动 9 步。这将"任意交换"的搜索空间压缩到了常数级别，从而把问题变成"每轮从前 10 个候选中贪心选最优"，用链表维护序列即可线性解决。

题解 | #交换到最大#

交换到最大

思路

代码

复杂度

总结