题目描述
思路解析
一句话答案：LeetCode 670 最大交换：最多对调一次两个数位、让整数尽量大。先记下每个数字最后出现的下标，再从最高位往右找第一个能被后面更大数字顶替的位、和最靠右的那个最大数字对调一次，时间 O(len)、空间 O(1)。
最多对调一次两个数位，能把整数抬到多大
给一个非负整数 num，允许挑其中两个数位对调一次，也允许一次都不换，要让最后得到的整数尽量大。题面给的 num = 2736，把 2 和 7 对调得到 7236；num = 9973 本身就是这几个数位能排出的最大值，一次都不用换、原样返回。数位最多 9 个，num 不超过一亿。
把每两位都试着对调一遍，哪里不划算
笨办法是枚举所有对调：任取两个位置换一下、拼出新整数，一路比下来留最大的那个。数位有 n 个就有大约 n×n／2 种对调，每种都得拼成整数比一次，是 O(len²)。位数最多 9，这么跑其实也能过，但它把每种对调都当成一样重要，漏掉一个直白的事实——越靠左的数位，一次变动对整数的影响越大，不必平等地全试一遍。
从最高位起，找第一个能被后面顶上来的数位
既然高位的话语权最大，就从最高位开始逐位看：只要当前这一位的后面存在严格更大、也就是 ＞ 当前数位的数字，就把那个更大的数字换上来，高位一变大，整个数立刻上一个台阶。贪心就落在高位优先上：一次对调的名额留给话语权最大的高位，从最高位数起第一个能被后面更大数字顶替的位就是下手处，把它右边出现过的最大数字换上来，整数一步抬到最高。
如果后面有好几个同样大的目标数字，要换最靠右的那一个：它腾出来的高位由更靠后的数位补上，剩下的整数比换靠前的同值数字更大。
用一张 last 表，把后面每个数字的最右位置查出来
先从左到右扫一遍，为每个数字记下它最后一次出现的下标，存进一张长度 10 的 last 表；同一个数字出现多次时，后写的下标盖掉先写的，留下的正是它最靠右那次的位置。再从最高位往右逐位处理：对当前数位，从 9 往下试每个更大的候选数字，一旦某个候选在 last 表里的下标落在当前位右边，就把它换上来、直接返回这个整数。第一次成功对调就收工——最多只能换一次，而从高位第一次命中的对调，已是所有一次对调里收益最大的。
2736 与 9973，两趟各换没换
拿 2736 走一遍。先建 last 表：数字 2 在下标 0，7 在 1，3 在 2，6 在 3。再从最高位看起，最高位是 2，从 9 往下找比 2 大又落在它右边的数字——7 出现在下标 1、正好在右边，且 7 ＞ 2，是能换到的最大数字，把最高位的 2 和这个 7 对调，得到 7236，立即返回。
9973 则相反：建好 last 表后从最高位逐位查，9、9、7、3 每一位往后都找不到更大的数字，一次都没换、原样交出 9973。
最容易把答案换坏的三处
找到更大的目标数字就换它第一次出现的位置，是最常见的写坏点：同样大的数字要换最靠右那个，换靠前的会把一个较大的位留在偏低处、整数反而更小。从低位往高位找也不行，低位换大对整数的抬升远不如高位，方向一反就拿不到最优。还有换完不肯停、继续往后找更优解：本题只能换一次，从高位第一次命中的对调已经封顶，接着换只会把到手的最大值改坏。整套流程扫两遍数位、每位最多看 10 个候选，位数不超过 9，全是常数级，时间 O(len)、空间 O(1)，last 表固定十格、与位数无关。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「高位换大、目标取最右」这两条贪心，下面每帧都在套它。
第一步:预处理。建一张 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题