LeetCode 670中等贪心
最大交换 图解题解
这道题到底在问什么
给定非负整数 num，最多交换其中两个数位一次，返回能得到的最大整数。可以不交换。
- 输入
- num = 2736
- 输出
- 7236 （交换 2 和 7）
- 输入
- num = 9973
- 输出
- 9973 （已是最大，不换）
- 输入
- num = 98368
- 输出
- 98863 （把第 3 位的 3 换到后面的 8）
最优解：一步一步想明白
- 3记住「高位换大、目标取最右」这两条贪心，下面每帧都在套它。
- 4第一步:预处理。建一张 last 表，记每个数字最后一次出现在哪个下标。先全置 -1。
- 5扫到下标 0 的数字 7，把 last[7] 更新为 0（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 6扫到下标 1 的数字 6，把 last[6] 更新为 1（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 7扫到下标 2 的数字 6，把 last[6] 更新为 2（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 8扫到下标 3 的数字 5，把 last[5] 更新为 3（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 9扫到下标 4 的数字 5，把 last[5] 更新为 4（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 10扫到下标 5 的数字 4，把 last[4] 更新为 5（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 11扫到下标 6 的数字 1，把 last[1] 更新为 6（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 12扫到下标 7 的数字 2，把 last[2] 更新为 7（后出现的会覆盖先前的，最终留下的就是最后下标）。
- 13last 表完工：数字 2 最后在下标 7，1 在 6，4 在 5，5 在 4（出现两次，记的是最右那次的下标 4），这正是后面贪心要的「最右目标」。
- 14轮到下标 0 的数字 7。从 9 往下逐个看：谁比 7 大、又出现在 0 的右边？
- 15数字 9 整串里没出现，没法用，看下一个更小的候选。
- 16数字 8 整串里没出现，没法用，看下一个更小的候选。
- 17下标 0 的 7 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
- 18轮到下标 1 的数字 6。从 9 往下逐个看：谁比 6 大、又出现在 1 的右边？
- 19数字 9 整串里没出现，没法用，看下一个更小的候选。
- 20数字 8 整串里没出现，没法用，看下一个更小的候选。
- 21数字 7 虽然更大，但它最后出现在下标 0，落在 1 的左边或同位，换过去高位反而变小，放弃。
- 22下标 1 的 6 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
- 23轮到下标 2 的数字 6。从 9 往下逐个看：谁比 6 大、又出现在 2 的右边？
- 24数字 9 整串里没出现，没法用，看下一个更小的候选。
- 25数字 8 整串里没出现，没法用，看下一个更小的候选。
- 26数字 7 虽然更大，但它最后出现在下标 0，落在 2 的左边或同位，换过去高位反而变小，放弃。
- 27下标 2 的 6 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
- 28轮到下标 3 的数字 5。从 9 往下逐个看：谁比 5 大、又出现在 3 的右边？
- 29数字 9 整串里没出现，没法用，看下一个更小的候选。
- 30数字 8 整串里没出现，没法用，看下一个更小的候选。
- 31数字 7 虽然更大，但它最后出现在下标 0，落在 3 的左边或同位，换过去高位反而变小，放弃。
- 32数字 6 虽然更大，但它最后出现在下标 2，落在 3 的左边或同位，换过去高位反而变小，放弃。
- 33下标 3 的 5 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
- 34轮到下标 4 的数字 5。从 9 往下逐个看：谁比 5 大、又出现在 4 的右边？
- 35数字 9 整串里没出现，没法用，看下一个更小的候选。
- 36数字 8 整串里没出现，没法用，看下一个更小的候选。
- 37数字 7 虽然更大，但它最后出现在下标 0，落在 4 的左边或同位，换过去高位反而变小，放弃。
- 38数字 6 虽然更大，但它最后出现在下标 2，落在 4 的左边或同位，换过去高位反而变小，放弃。
- 39下标 4 的 5 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
- 40轮到下标 5 的数字 4。从 9 往下逐个看：谁比 4 大、又出现在 5 的右边？
- 41数字 9 整串里没出现，没法用，看下一个更小的候选。
- 42数字 8 整串里没出现，没法用，看下一个更小的候选。
- 43数字 7 虽然更大，但它最后出现在下标 0，落在 5 的左边或同位，换过去高位反而变小，放弃。
- 44数字 6 虽然更大，但它最后出现在下标 2，落在 5 的左边或同位，换过去高位反而变小，放弃。
- 45数字 5 虽然更大，但它最后出现在下标 4，落在 5 的左边或同位，换过去高位反而变小，放弃。
- 46下标 5 的 4 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
- 47轮到下标 6 的数字 1。从 9 往下逐个看：谁比 1 大、又出现在 6 的右边？
- 48数字 9 整串里没出现，没法用，看下一个更小的候选。
- 49数字 8 整串里没出现，没法用，看下一个更小的候选。
- 50数字 7 虽然更大，但它最后出现在下标 0，落在 6 的左边或同位，换过去高位反而变小，放弃。
- 51数字 6 虽然更大，但它最后出现在下标 2，落在 6 的左边或同位，换过去高位反而变小，放弃。
- 52数字 5 虽然更大，但它最后出现在下标 4，落在 6 的左边或同位，换过去高位反而变小，放弃。
- 53数字 4 虽然更大，但它最后出现在下标 5，落在 6 的左边或同位，换过去高位反而变小，放弃。
- 54数字 3 整串里没出现，没法用，看下一个更小的候选。
- 55找到了！数字 2 最后出现在下标 7，在 6 的右边，且 2 > 1。这是高位能换到的最大数字、又取了最靠右的它，立即交换。
- 56交换后高位的 1 变成了 2，整数从 76655412 变成 76655421。第一次成功交换就直接返回，绝不再换第二次。
⚠️ 容易写错的地方
✗ 错：找到更大数字就换第一个出现的位置
✓ 对：要换「最后出现」的位置
同样大的目标，换最右那个让出的位置最低、整数最大，所以要用 last 记最右下标
✗ 错：从低位开始换
✓ 对：从高位开始，越靠左换大收益越高
高位每变大一档，对整数的影响远大于低位
✗ 错：交换后继续往后找更优解
✓ 对：第一次成功交换后立即返回
本题最多只能换一次；从高位第一次命中的交换已是所有一次交换方案里的最优，所以必须立即返回
完整代码（Python / C++ / Java）
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 numC++
#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;
}
}复杂度
时间
O(d)
d 是位数(≤9):扫一遍建表,再扫一遍每位最多看 9 个候选,都是常数级
空间
O(1)
last 表固定 10 个槽,与位数无关
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大交换 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不预处理 last 表，直接对每位往右暴力找最大可以吗？复杂度如何？+
可以，对每位扫它右边找最大且最靠右的数字，是 O(d²)。位数最多 9，实战没差别；但用长度 10 的 last 表把它压到 O(d)，思路也更清晰：先记每个数字最后位置，再从高位贪心找更大的。
如果允许交换任意多次（不只一次），答案会怎样？+
那就退化成「把所有数位从大到小排序」，直接得到该数位集合能组成的最大数。本题限制「最多一次」，才需要这套高位贪心 + 目标取最右的策略。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大交换 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。