LeetCode 670. 最大交换

约 4 分钟
文章信息 11 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 腾讯 字节 阿里 华为 快手 虾皮
标签
数学 贪心

题目描述

✅ 670. 最大交换

image-20260928204505575

题意分析

给定一个非负整数，最多选择两个数位交换一次，使结果尽可能大，返回这个最大整数。各个数字的数量不变，不能任意重排，也不能连续进行多次交换。

“最多一次”允许完全不交换。如果没有任何交换能让结果更大，就保留原数。题目输入不超过 10^8，数位重排后的结果仍能用 32 位有符号整数保存。

解法：记录数字最后位置的贪心交换

核心思路

[!blue]

等长数字从高位向低位比较，第一个不同位置就决定大小。因此，只要某个位置能换入右侧更大的数字，就应该优先改善最靠左的这种位置；只修改它后面的低位，收益一定更小。

确定位置后，应换入它右侧最大的数字，否则在这个最早变化的位置就输给了更大的候选。若最大的数字出现多次，应选择最右边的那个：换入的高位完全相同，但选择更右的位置，可以保留前面的较大数字，把被换走的小数字放到更低位。

数字只有 0 到 9，先用 last[d] 记录每种数字最后出现的下标，就能直接找到所需交换位置。随后从左到右枚举当前数位 cur，从 9 向 cur + 1 检查；第一个满足 last[d] > i 的数字，就是右侧最大的候选及其最右位置。

完成这一对交换后立即返回，已经同时做到“改动最早的可提升高位、换入最大数字、把损失推到最右”。若扫描结束都没有候选，任何数位右侧都没有更大的数字，当前排列已不能通过一次交换增大。

解题步骤

  1. 将整数转换为数位数组，从左到右更新每种数字的最后出现位置。
  2. 从最高位开始枚举当前位置 i 和数字 cur。
  3. 依次检查比 cur 大的数字，顺序从 9 到 cur + 1。
  4. 找到 last[digit] > i 时，交换当前位置和该最后位置，转换成整数并立即返回。
  5. 所有位置都无法改善时返回原数。

代码实现

class Solution {
    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 digit = 9; digit > cur; digit--) {
                // 最早能提升的高位优先，选择更大数字最右出现让换回的小值尽量靠后。
                if (last[digit] > i) {
                    char value = digits[i];

                    digits[i] = digits[last[digit]];
                    digits[last[digit]] = value;

                    return Integer.parseInt(new String(digits));
                }
            }
        }

        return num;
    }
}

import "strconv"

func maximumSwap(num int) int {
    digits := []byte(strconv.Itoa(num))
    last := make([]int, 10)
    for i := 0; i < len(digits); i++ {
        last[digits[i]-'0'] = i
    }

    for i := 0; i < len(digits); i++ {
        cur := int(digits[i] - '0')
        for digit := 9; digit > cur; digit-- {
            // 最早能提升的高位优先，选择更大数字最右出现让换回的小值尽量靠后。
            if last[digit] > i {
                digits[i], digits[last[digit]] = digits[last[digit]], digits[i]
                ans, _ := strconv.Atoi(string(digits))
                return ans
            }
        }
    }
    return num
}

复杂度分析

设十进制数位数为 $d$。

  • 时间复杂度：$O(d)$。每个位置最多检查九种候选数字，构造与解析数位也只需线性时间。
  • 辅助空间复杂度：$O(d)$，用于保存数位数组；长度为十的位置表占常数空间。

关键点总结

[!green]

  • 先选择最靠左的可改善位置，再选择右侧最大的数字。
  • 相同候选取最右位置，才能把换回的小数字造成的影响推到最低位。
  • 最后位置表一次预处理即可完成所有候选查询，不需要排序。

易错点总结

[!yellow]

  • 相同大数字若取第一次出现的位置，会过早放入被换走的小数字，使结果小于选择最右位置的方案。
  • 候选必须严格大于当前数字；若先交换相等数字并返回，会浪费唯一一次交换机会。
  • 必须检查 last[digit] > i，确保候选在右侧；位置表默认值为零也会被这个条件自然排除。
  • 一旦完成交换就要返回，继续修改会违反最多交换一次的限制。
  • 找不到可提升位置时无需强制交换，原数就是答案。

相似题目

题目 难度 关联与区别
31. 下一个排列 中等 原题求最接近的更大排列，本题只允许一次交换并求最大值，不能直接执行下一排列。
1323. 6 和 9 组成的最大数字 简单 同样优先改善最高位，原题只能把某个6变9，本题还要从后面选择交换来源。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/68769992
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！