最大交换如何用贪心得到最大数字？为什么要和最靠右的大数字交换？

简化版

最大交换只允许交换一次。贪心策略是从左到右找第一个能被右侧更大数字替换的位置；为了让结果最大，应选择右侧最大的数字，并且若有多个相同最大数字，选择最靠右的那个交换。

详细版

可以先记录每个数字 0..9 最后出现的位置。然后从左到右扫描当前位 d，尝试从 9 到 d+1 查找是否有更大数字出现在右侧。如果找到，就交换当前位和那个更大数字的最后位置，立即返回。

因为越靠左的位权越大，所以第一次能提升的位置最关键；同一个更大数字选择最靠右位置，能让被换下去的小数字尽量靠后。时间复杂度 O(10n)，可视作 O(n)。

完整版教学

一、为什么只关心最左边能提升的位置

数字大小由高位优先决定。只允许交换一次时，最划算的事情一定是尽量提升靠左的位置。比如 2736，把 2 和 7 换成 7236，比把后面的 3 和 6 换成 2763 大得多。

7236
2763
^ 第一位已经决定胜负

因此扫描时一旦找到某个位置能变大，就应该在这个位置完成交换并返回。

二、为什么要找右侧最大数字

对于当前位置 i，如果右侧有多个比它大的数字，当然应该换最大的。比如当前是 2，右侧有 7 和 9，换 9 得到的高位更大。

当前位	可交换右侧数字	最优选择
2	7、9	9
4	5、8	8

记忆钩子：一次交换要把“最靠左的坑”补到尽可能大。

这就是从 9 往当前数字上方枚举的原因。

三、为什么相同大数字选最靠右的

如果右侧有多个相同的最大数字，选择最靠右的那个更好。因为当前较小数字会被换到那个位置，放得越靠右，对整体影响越小。

num = 1993
交换第一个 1 和第一个 9：9193
交换第一个 1 和第二个 9：9913

显然 9913 更大，所以要记录每个数字最后出现的位置。

四、如何记录最后位置

数字只有 10 种，可以用长度为 10 的数组：

last[d] = 数字 d 最后一次出现的下标

例如 98368：

last[8] = 4
last[9] = 0
last[3] = 2
last[6] = 3

扫描每个位置时，查看 9 到 当前数字+1 是否存在于右侧即可。

五、代码模板

int maximumSwap(int num) {
    char[] arr = String.valueOf(num).toCharArray();
    int[] last = new int[10];
    for (int i = 0; i < arr.length; i++) {
        last[arr[i] - '0'] = i;
    }
    for (int i = 0; i < arr.length; i++) {
        int cur = arr[i] - '0';
        for (int d = 9; d > cur; d--) {
            if (last[d] > i) {
                char tmp = arr[i];
                arr[i] = arr[last[d]];
                arr[last[d]] = tmp;
                return Integer.parseInt(new String(arr));
            }
        }
    }
    return num;
}

last[d] > i 保证更大数字在当前位右侧。如果数字已经是降序，比如 9973，循环不会交换，直接返回原数。

六、用例子推演

num=2736：

last[7]=1, last[6]=3, last[3]=2, last[2]=0
扫描 i=0，当前 2
从 9 查到 7，发现 last[7]=1 > 0
交换 2 和 7，得到 7236

num=1993：

i=0，当前 1
last[9]=2
交换下标 0 和 2，得到 9913

这正体现了“右侧最大 + 最靠右”的双重选择。

七、常见误区与追问

误区：交换全局最大和全局最小。 最小数字如果不在高位，交换未必最优。
误区：相同最大数字选第一个。 应选最靠右的相同最大数字，让小数字尽量后移。
误区：找到可交换后继续尝试后面位置。 最左提升位最重要，完成后应立即返回。
追问：为什么复杂度是 O(n)？ 每位最多检查 10 个数字，常数为 10。
追问：如果允许多次交换呢？ 问题会变成排序或更复杂的交换约束，不再是这个贪心。
追问：输入为 0 怎么办？ 转成字符数组后不会交换，返回 0。

八、加强记忆

最大交换的口诀是“最左能变大，右侧找最大；相同选最右，交换就收手”。高位优先决定了为什么从左扫，最后位置数组决定了为什么能找最右最大数字。别做全局最大最小交换，那是这题最常见的误判。

简化版

详细版