最大交换 图解题解

最多对调一次两个数位，能把整数抬到多大

给一个非负整数 num，允许挑其中两个数位对调一次，也允许一次都不换，要让最后得到的整数尽量大。题面给的 num = 2736，把 2 和 7 对调得到 7236；num = 9973 本身就是这几个数位能排出的最大值，一次都不用换、原样返回。数位最多 9 个，num 不超过一亿。

把每两位都试着对调一遍，哪里不划算

笨办法是枚举所有对调：任取两个位置换一下、拼出新整数，一路比下来留最大的那个。数位有 n 个就有大约 n×n／2 种对调，每种都得拼成整数比一次，是 O(len²)。位数最多 9，这么跑其实也能过，但它把每种对调都当成一样重要，漏掉一个直白的事实——越靠左的数位，一次变动对整数的影响越大，不必平等地全试一遍。

从最高位起，找第一个能被后面顶上来的数位

既然高位的话语权最大，就从最高位开始逐位看：只要当前这一位的后面存在严格更大、也就是 ＞ 当前数位的数字，就把那个更大的数字换上来，高位一变大，整个数立刻上一个台阶。贪心就落在高位优先上：一次对调的名额留给话语权最大的高位，从最高位数起第一个能被后面更大数字顶替的位就是下手处，把它右边出现过的最大数字换上来，整数一步抬到最高。

如果后面有好几个同样大的目标数字，要换最靠右的那一个：它腾出来的高位由更靠后的数位补上，剩下的整数比换靠前的同值数字更大。

用一张 last 表，把后面每个数字的最右位置查出来

先从左到右扫一遍，为每个数字记下它最后一次出现的下标，存进一张长度 10 的 last 表；同一个数字出现多次时，后写的下标盖掉先写的，留下的正是它最靠右那次的位置。再从最高位往右逐位处理：对当前数位，从 9 往下试每个更大的候选数字，一旦某个候选在 last 表里的下标落在当前位右边，就把它换上来、直接返回这个整数。第一次成功对调就收工——最多只能换一次，而从高位第一次命中的对调，已是所有一次对调里收益最大的。

2736 与 9973，两趟各换没换

拿 2736 走一遍。先建 last 表：数字 2 在下标 0，7 在 1，3 在 2，6 在 3。再从最高位看起，最高位是 2，从 9 往下找比 2 大又落在它右边的数字——7 出现在下标 1、正好在右边，且 7 ＞ 2，是能换到的最大数字，把最高位的 2 和这个 7 对调，得到 7236，立即返回。

9973 则相反：建好 last 表后从最高位逐位查，9、9、7、3 每一位往后都找不到更大的数字，一次都没换、原样交出 9973。

最容易把答案换坏的三处

找到更大的目标数字就换它第一次出现的位置，是最常见的写坏点：同样大的数字要换最靠右那个，换靠前的会把一个较大的位留在偏低处、整数反而更小。从低位往高位找也不行，低位换大对整数的抬升远不如高位，方向一反就拿不到最优。还有换完不肯停、继续往后找更优解：本题只能换一次，从高位第一次命中的对调已经封顶，接着换只会把到手的最大值改坏。整套流程扫两遍数位、每位最多看 10 个候选，位数不超过 9，全是常数级，时间 O(len)、空间 O(1)，last 表固定十格、与位数无关。

Python

class Solution:
    def maximumSwap(self, num: int) -> int:
        arr = list(str(num))
        last = {int(ch): i for i, ch in enumerate(arr)}
        for i, ch in enumerate(arr):
            d = int(ch)
            for bigger in range(9, d, -1):
                if last.get(bigger, -1) > i:
                    j = last[bigger]
                    arr[i], arr[j] = arr[j], arr[i]
                    return int(''.join(arr))
        return num

C++

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        vector<int> last(10, -1);
        for (int i = 0; i < (int)s.size(); ++i) last[s[i]-'0'] = i;
        for (int i = 0; i < (int)s.size(); ++i) {
            for (int d = 9; d > s[i]-'0'; --d) {
                if (last[d] > i) {
                    swap(s[i], s[last[d]]);
                    return stoi(s);
                }
            }
        }
        return num;
    }
};

Java

import java.util.*;
class Solution {
    public int maximumSwap(int num) {
        char[] s = String.valueOf(num).toCharArray();
        int[] last = new int[10];
        Arrays.fill(last, -1);
        for (int i = 0; i < s.length; i++) last[s[i] - '0'] = i;
        for (int i = 0; i < s.length; i++) {
            for (int d = 9; d > s[i] - '0'; d--) {
                if (last[d] > i) {
                    char t = s[i]; s[i] = s[last[d]]; s[last[d]] = t;
                    return Integer.parseInt(new String(s));
                }
            }
        }
        return num;
    }
}