LeetCode"最大交换"题解：用贪心算法优化面试中数字交换问题

下午刷到个HR的吐槽，说面试了一堆985、211的研究生，抢一个每月6500元的基础岗位，结果最后却录了一个普通二本的学生。这事儿听着就透着股魔幻现实主义的味儿。

现在这找工作的行情，跟抢春运回城票差不多，甭管坐票站票，能上车就是好票。用服务器的算力去运行一个“Hello World”，大概就是这么个感觉。

不过话说回来，HR最后选了二本生，其实也不难理解。基础岗求的就是稳定、踏实、能快速上手干活。真想缓解这种“疯狂”的内卷，或许招聘方把技能要求和岗位测评写得更清晰些会更好，让候选人少走弯路，双方都省下加班面试的功夫。

说到面试，正好分享一个挺有意思的算法题——最大交换。这题目的场景你细品一下，还挺有职场隐喻的。

面试题：最大交换

昨晚快下班，领导路过我工位，手一拍我肩膀：“东哥，来个简单的算法题放松一下，大不了明天不用来上班。”我当时心里就咯噔一下，这话术听着就相当不简单。

题目是这样的：给你一个非负整数，你最多只能交换其中两个数字一次，目的是让交换后的数字尽可能大。比如给你 2736，交换 2 和 7 之后得到 7236，这就是答案。

是不是很像老板说：“咱们团队架构不动，就调两个人的岗，给我把整体效益提到最高”？这熟悉的味道一下子就上来了。

思路一：暴力枚举法

我脑子里蹦出来的第一个方案，就是最直接的暴力破解。数字总共也没几位，我把所有两个位置的组合都枚举一遍，全部交换试试看，哪个结果最大就选哪个。用代码实现，大概长这样：

public int maximumSwapBruteForce(int num) {
    char[] arr = String.valueOf(num).toCharArray();
    int n = arr.length;
    int best = num;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(arr, i, j);
            int cur = Integer.parseInt(new String(arr));
            if (cur > best) {
                best = cur;
            }
            swap(arr, i, j); // 换回去
        }
    }
    return best;
}

private void swap(char[] arr, int i, int j) {
    char t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

这个写法对付小的数字没问题，面试官心情好或许也能让你过。但你想想，如果这个数字长度上去了，比如是一个10万位的大整数（虽然int存不下，但思路如此），这套双层 for 循环下来，计算量可是 O(n²)，那感觉就像是没调优 SpringBoot 配置直接扔上生产环境，服务器分分钟给你表演个“原地升天”。

所以，必须换个思路。

思路二：贪心算法

我们想要“最大”，直觉是什么？是不是数字的高位（靠左的位）越关键？让第一位变大一点，其收益远超过让最后一位变大。这其实就是典型的“贪心”思想——在每一步都做出当下看起来最好的选择。

那么问题就转化了：对于从左到右的每一位数字，我要问它一句：“在你后面，有没有比我大的数字？如果有，请把那个最大的，并且最靠右的，换过来和我交换。”

为什么要找“最靠右的最大值”？举个例子：1 9 8 9，第一位 1 想和后面的 9 交换。后面有两个 9，你换左边那个还是右边那个？答案是换最右边那个。因为这样交换后，左边还能留下一个 9，对整体的“数值友好度”更高，对后面数位结构的破坏也更小。

为了实现这个思路，我们需要预先知道：对于数字 0 到 9，它们最后一次出现在哪个下标。这个很简单，从左到右扫描一遍数字字符串，不断更新每个数字最后一次出现的位置即可。

基于贪心思想的核心代码如下：

public int maximumSwap(int num) {
    char[] digits = String.valueOf(num).toCharArray();
    int n = digits.length;
    // 记录每个数字（0-9）最后一次出现的位置
    int[] last = new int[10];
    for (int i = 0; i < n; i++) {
        int d = digits[i] - '0';
        last[d] = i;
    }

    // 从左往右，尝试为每一位找到能换来最大收益的数字
    for (int i = 0; i < n; i++) {
        int cur = digits[i] - '0';
        // 从9开始往下找，找比当前位大的数字
        for (int d = 9; d > cur; d--) {
            if (last[d] > i) { // 后面真的存在更大的数字d
                char tmp = digits[i];
                digits[i] = digits[last[d]];
                digits[last[d]] = tmp;
                return Integer.parseInt(new String(digits));
            }
        }
    }
    // 没找到可交换的，说明原数字已经是“最大状态”
    return num;
}

这个版本就高效多了。第一次扫描记录位置，O(n)。第二次扫描尝试交换，内层循环最多查10次（数字0-9），还是O(n)。整体时间复杂度是线性的。这好比把“全公司两两调岗”的混乱局面，变成了“每个人只向上看10级领导有没有坑位”，效率立竿见影。

测试一下效果

我写了个简单的测试来验证，控制台输出的画面感很强：

public static void main(String[] args) {
    System.out.println(debugSwap(2736));   // 7236
    System.out.println(debugSwap(9973));   // 9973
    System.out.println(debugSwap(109090)); // 910090
}

static int debugSwap(int num) {
    System.out.println("原始数字：" + num);
    int ans = new 最大交换工具().maximumSwap(num);
    System.out.println("交换后：" + ans);
    System.out.println("----");
    return ans;
}

static class 最大交换工具 {
    public int maximumSwap(int num) {
        char[] digits = String.valueOf(num).toCharArray();
        int[] last = new int[10];
        for (int i = 0; i < digits.length; i++) {
            last[digits[i] - '0'] = i;
        }
        for (int i = 0; i < digits.length; i++) {
            int cur = digits[i] - '0';
            for (int d = 9; d > cur; d--) {
                if (last[d] > i) {
                    char t = digits[i];
                    digits[i] = digits[last[d]];
                    digits[last[d]] = t;
                    return Integer.parseInt(new String(digits));
                }
            }
        }
        return num;
    }
}

我们来脑补一下控制台的运行逻辑：

• 2736：第一位 2 发现后面有 7（从9查到3，发现7比2大，且7最后出现在下标2）。果断和那个 7 交换，变成 7236，游戏结束。
• 9973：第一位 9 往后看，最大的也是 9，但后面的 9 出现在下标1，不比当前下标0大（last[9]=1 > 0 成立，但 d=9 并不 > cur=9，所以不交换）。第二位 9 往后看，只有 7 和 3，都比它小。这已经是“人生巅峰”配置，无需变动。
• 109090：这个有点意思。首位 1 往后看，能找到数字 9，而且最后一个 9 出现在下标4（last[9]=4 > 0）。于是把 1 和那个 9 交换，变成 910090，瞬间就显“阔气”了。

核心总结

写到这你会发现，这道题的解题关键就两点：

1. 尽早动手：从左向右扫描，一旦找到机会（当前位后面有更大的数）就立即交换，体现“贪心”的精髓——局部最优。
2. 换就换最好的：要换就换后面最大的数字，并且要挑那个最靠右的来换，以最大化交换后的整体收益。这思路是不是很“社会”？

实际工作中很多事也类似。像 SpringBoot、数据库连接池、消息队列的默认配置，如果不去根据实际场景动手调优，迟早会在某个临界点给你来个“惊喜”。这个教训，很多人都是在生产环境的“实践教学”中学到的。

好了，题解思路就是这些。如果你想用 Python、Go 等其他语言实现，只需把这套贪心逻辑翻译过去即可，核心思路别换，解题就稳了。技术之路，很多时候就是在纷繁复杂的表象下，找到那个最直接有效的“贪心”策略。