LeetCode 670. 最大交换
目录
题目描述
题意分析
给定一个非负整数，允许在它的十进制表示上任选两个位置把数字对调，最多只能做一次，问能得到的最大数是多少。
「最多一次」是关键约束：可以交换一次，也可以一次都不换。如果原数本身已经是它所有位重排里最大的（也就是各位从高到低非递增），那么任何交换都只会让它变小，此时答案就是原数。
由于只允许一次交换，位数在过程中不会变化，也不会出现前导零的问题——最高位若参与交换，换过去的一定是更大的数字，不可能是 0。
边界包括：一位数，此时无从交换；各位全部相同的数如
1111；已经严格递减的数如9973；以及存在多个相同最大数字的数如1993。
解法：记录数字最后位置的贪心交换
核心思路
一次交换得到的两个结果，先看从左到右第一个不同的数位；该位更大的结果一定更大。因此应优先提升最靠左、且右侧存在更大数字的位置，而不是枚举所有位置对。
先记录数字
0..9最后出现的位置。随后从左到右扫描当前位i，再从 9 向下寻找右侧可用且比当前位大的数字。第一个命中的数字最大；若它出现多次，选择最靠右的位置，让被换走的小数字尽量落在低位，结果才最大。扫描不变量是：到达
i时，i左侧不存在任何可使结果变大的交换，因此这些高位已经确定。若在i找到目标，交换后第一个变化的位置取得了能放入的最大数字，且剩余损失被推到最右侧，所以它优于所有其他一次交换，可以立即返回；若始终找不到，原数已经按位非递增，保持不变最优。
解题步骤
- 把整数转为数位数组，并记录每个数字最后一次出现的下标。
- 从高位到低位遍历下标
i。- 对当前数字
cur，从 9 递减检查到cur + 1；last[digit] > i表示右侧有可交换的更大数字。- 命中后与该数字的最后位置交换并立即返回。
- 全部位置都未命中时，不做交换，返回原数。
2736在最高位找到右侧最大的 7，得到7236；1993要选择最后一个 9，得到9913，而不是与第一个 9 交换得到的9193。
代码实现
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
}
复杂度分析
- 时间复杂度：$O(d)$，$d$ 为数位数；每一位最多检查 9 个固定候选数字。
- 空间复杂度：$O(d)$，用于保存数位数组；长度为 10 的位置表是 $O(1)$。
关键点总结
- 比较等长数字时，最高的不同位决定大小，所以优先提升最左位置。
- 换入右侧最大数字；相同数字取最后位置，把小数字造成的损失推到最低位。
- 数字值域只有 10 个，用固定位置表即可常数时间查询，无需排序。
- “最多一次”包括不交换；已经非递增的数必须原样返回。
易错点总结
- 相同大数字取第一次出现：
1993会得到9193，正确结果是与最后一个 9 交换得到9913。- 允许交换相等数字：
919若先交换两个 9 会提前返回原数，错过991；候选必须严格大于当前位。- 只判断数字是否出现：位置必须满足
last[digit] > i，否则可能使用左侧数字或当前位置。- 命中后继续交换：题目最多交换一次，完成最优交换后必须立即返回。
- 强制进行交换：
9973已经最优，找不到可提升位置时应返回原数。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 31. 下一个排列 | 中等 | 求「恰好大一点」而非最大，需从低位找拐点 |
| 556. 下一个更大元素 III | 中等 | 下一个排列套在数位上，还要判 32 位溢出 |
| 402. 移掉 K 位数字 | 中等 | 操作是删除而非交换，用单调栈维护递增前缀 |
| 321. 拼接最大数 | 困难 | 两数组分配长度后各取最大子序列再归并 |
| 12. 整数转罗马数字 | 中等 | 同样按数位贪心，但贪的是面值而非位置 |