题目描述
思路解析动画文字版
记住「高位换大、目标取最右」这两条贪心，下面每帧都在套它。
第一步:预处理。建一张 last 表，记每个数字最后一次出现在哪个下标。先全置 -1。
扫到下标 0 的数字 7，把 last[7] 更新为 0（后出现的会覆盖先前的，最终留下的就是最后下标）。
扫到下标 1 的数字 6，把 last[6] 更新为 1（后出现的会覆盖先前的，最终留下的就是最后下标）。
扫到下标 2 的数字 6，把 last[6] 更新为 2（后出现的会覆盖先前的，最终留下的就是最后下标）。
扫到下标 3 的数字 5，把 last[5] 更新为 3（后出现的会覆盖先前的，最终留下的就是最后下标）。
扫到下标 4 的数字 5，把 last[5] 更新为 4（后出现的会覆盖先前的，最终留下的就是最后下标）。
扫到下标 5 的数字 4，把 last[4] 更新为 5（后出现的会覆盖先前的，最终留下的就是最后下标）。
扫到下标 6 的数字 1，把 last[1] 更新为 6（后出现的会覆盖先前的，最终留下的就是最后下标）。
扫到下标 7 的数字 2，把 last[2] 更新为 7（后出现的会覆盖先前的，最终留下的就是最后下标）。
last 表完工：数字 2 最后在下标 7，1 在 6，4 在 5，5 在 4（出现两次，记的是最右那次的下标 4），这正是后面贪心要的「最右目标」。
轮到下标 0 的数字 7。从 9 往下逐个看：谁比 7 大、又出现在 0 的右边？
数字 9 整串里没出现，没法用，看下一个更小的候选。
数字 8 整串里没出现，没法用，看下一个更小的候选。
下标 0 的 7 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
轮到下标 1 的数字 6。从 9 往下逐个看：谁比 6 大、又出现在 1 的右边？
数字 9 整串里没出现，没法用，看下一个更小的候选。
数字 8 整串里没出现，没法用，看下一个更小的候选。
数字 7 虽然更大，但它最后出现在下标 0，落在 1 的左边或同位，换过去高位反而变小，放弃。
下标 1 的 6 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
轮到下标 2 的数字 6。从 9 往下逐个看：谁比 6 大、又出现在 2 的右边？
数字 9 整串里没出现，没法用，看下一个更小的候选。
数字 8 整串里没出现，没法用，看下一个更小的候选。
数字 7 虽然更大，但它最后出现在下标 0，落在 2 的左边或同位，换过去高位反而变小，放弃。
下标 2 的 6 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
轮到下标 3 的数字 5。从 9 往下逐个看：谁比 5 大、又出现在 3 的右边？
数字 9 整串里没出现，没法用，看下一个更小的候选。
数字 8 整串里没出现，没法用，看下一个更小的候选。
数字 7 虽然更大，但它最后出现在下标 0，落在 3 的左边或同位，换过去高位反而变小，放弃。
数字 6 虽然更大，但它最后出现在下标 2，落在 3 的左边或同位，换过去高位反而变小，放弃。
下标 3 的 5 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
轮到下标 4 的数字 5。从 9 往下逐个看：谁比 5 大、又出现在 4 的右边？
数字 9 整串里没出现，没法用，看下一个更小的候选。
数字 8 整串里没出现，没法用，看下一个更小的候选。
数字 7 虽然更大，但它最后出现在下标 0，落在 4 的左边或同位，换过去高位反而变小，放弃。
数字 6 虽然更大，但它最后出现在下标 2，落在 4 的左边或同位，换过去高位反而变小，放弃。
下标 4 的 5 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
轮到下标 5 的数字 4。从 9 往下逐个看：谁比 4 大、又出现在 5 的右边？
数字 9 整串里没出现，没法用，看下一个更小的候选。
数字 8 整串里没出现，没法用，看下一个更小的候选。
数字 7 虽然更大，但它最后出现在下标 0，落在 5 的左边或同位，换过去高位反而变小，放弃。
数字 6 虽然更大，但它最后出现在下标 2，落在 5 的左边或同位，换过去高位反而变小，放弃。
数字 5 虽然更大，但它最后出现在下标 4，落在 5 的左边或同位，换过去高位反而变小，放弃。
下标 5 的 4 右边找不到更大的数字，说明它已在最优位置，跳到下一位继续。
轮到下标 6 的数字 1。从 9 往下逐个看：谁比 1 大、又出现在 6 的右边？
数字 9 整串里没出现，没法用，看下一个更小的候选。
数字 8 整串里没出现，没法用，看下一个更小的候选。
数字 7 虽然更大，但它最后出现在下标 0，落在 6 的左边或同位，换过去高位反而变小，放弃。
数字 6 虽然更大，但它最后出现在下标 2，落在 6 的左边或同位，换过去高位反而变小，放弃。
数字 5 虽然更大，但它最后出现在下标 4，落在 6 的左边或同位，换过去高位反而变小，放弃。
数字 4 虽然更大，但它最后出现在下标 5，落在 6 的左边或同位，换过去高位反而变小，放弃。
数字 3 整串里没出现，没法用，看下一个更小的候选。
找到了！数字 2 最后出现在下标 7，在 6 的右边，且 2 > 1。这是高位能换到的最大数字、又取了最靠右的它，立即交换。
交换后高位的 1 变成了 2，整数从 76655412 变成 76655421。第一次成功交换就直接返回，绝不再换第二次。
边界先想清：单位数或已最大就原样返回；1993 体现「目标取最右的 9」。
两个高频追问：暴力 vs last 表、以及「一次」限制带来的本质区别。
参考代码
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复杂度
- 时间：O(d)，d 是位数(≤9):扫一遍建表,再扫一遍每位最多看 9 个候选,都是常数级
- 空间：O(1)，last 表固定 10 个槽,与位数无关
易错点
面试追问把动画讲成自己的话
追问不预处理 last 表，直接对每位往右暴力找最大可以吗？复杂度如何？
追问如果允许交换任意多次（不只一次），答案会怎样？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
有效的括号字符串
LeetCode 678 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题