题目描述
思路解析
一句话答案：LeetCode 1850 邻位交换的最小次数：先对 num 连做 k 次「下一个排列」求出第 k 个最小妙数，再数把 num 逐位挪成它的相邻交换次数（正好等于逆序对数），时间 O(k·n+n²)、空间 O(n)。
妙数是什么，这道题的两步分别求什么
给一个用字符串表示的大整数 num 和整数 k。把 num 各位数字重排，只要排出的数值比 num 大，就算一个「妙数」；妙数很多，只关心最小的几个。分两步：先找第 k 个最小妙数当目标串，再算把 num 变成它、每次只能换相邻两位、最少换几次。题面 num 为 1234、k 取 3 时，第 3 个最小妙数是 1342，答案 2 次。
把全部排列列出来挑第 k 个，为什么走不通
n 位数字全排列有 n! 种，全摊开挑比 num 大的、排序取第 k 个，n 才到 10 就三百多万种，二十位是天文数字，列不完。既然只要紧挨 num 往上的第 k 个，就该能从 num 一步步跳到下一个更大排列，不必铺开全部。
下一个排列怎么求，交换次数又凭什么等于逆序对
第一步靠「下一个排列」：求出比当前大、又是更大排列里最小的那个，即字典序上紧挨着的后一个。三步——从右往左找第一个比右邻小的位置叫拐点；再从右往左找第一个比拐点大的位置，两者交换；把拐点后的后缀反转成升序。从 num 连做 k 次，依次得第 1 到第 k 个最小妙数。
第二步只能换相邻两位。把目标每一位来自原串的哪个下标排成一串——逆序对，指这串里前面的数比后面的大的一对。一次相邻交换只调换相邻两个、至多消掉一个逆序对，所以最少次数正好等于这串下标的逆序对数。数字有重复时，相同数字要按原串里的先后去对应，才不会多造逆序对。
1234 连做三次下一个排列，怎样逼出 1342
从 1234 求第 1 个：拐点是下标 2 的 3，从右找第一个比 3 大的即下标 3 的 4，交换得 1243，后缀一位反转不变。在 1243 求第 2 个：拐点退到下标 1 的 2，和下标 3 的 3 交换得 1342，后缀 42 是降序，反转成 24 才得 1324——这步别省，不反转就跳过 1324。在 1324 求第 3 个：拐点是下标 2 的 2，和下标 3 的 4 交换得 1342，后缀不变即目标。
把 1234 挪成 1342，两次交换是怎么数出来的
目标 1342 的四位分别来自原串 1234 的下标 0、2、3、1。逐位对齐：第 0 位要 1，下标 0 已是 1；第 1 位要 3，3 在下标 2，换到下标 1，串变 1324，计 1 次；第 2 位要 4，4 在下标 3，换到下标 2，串变 1342，计 2 次；第 3 位要 2 已就位，共 2 次。换个角度数下标串 0、2、3、1 的逆序对：2 比 1、3 比 1 各一对，也是 2。
后缀忘反转、重复数字乱配，答案就跟着错
复杂度上，第一步 k 次下一个排列各扫一遍，是 O(k·n)；第二步双重循环数逆序对，是 O(n²)，合计 O(k·n+n²)。逆序对换树状数组可降到 O(n log n)。额外只有下标桶和位置数组，空间 O(n)。
下一个排列最阴的是反转后缀：交换完拐点直接用，会跳过更小的妙数、第 k 个整串错位。有重复也藏坑——像 11112 求第 4 个得 21111、答案 4，那几个 1 得按原串先后对应，乱配就多造逆序对。还有别混：数的是相邻交换、等于逆序对数，任意位置能换几步就排好，那是另一道题。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
两步套路:先用「下一个排列」做 k 次求出第 k 个最小妙数(找拐点 i、找 j 交换、反转后缀);再用冒泡把 num 逐位对齐到目标、累加相邻交换次数(等于逆序对数)。下面每帧都在套它。
总览 · 先求目标再数代价：先看清画面。上面这排格子是 num 等于 1234,四位数字 1、2、3、4,下标 0 到 3。任务分两步:第一步反复求「下一个排列」3 次,拿到第 3 个最小妙数当目标;第二步再数从 1234 挪到那个目标,最少要几次相邻交换。右边面板先记第一步:已经求到第几个妙数、当前排列长什么样、这一步在做什么。
第 1 次下一排列 · 找拐点 i：求第 1 个最小妙数。从最右边往左看,找第一个「比它右邻小」的位置,这就是拐点。下标 3 是 4,它右边没有邻居;看下标 2 的 3,它右边是 4,3 小于 4,拐点就是它,i 等于 2,绿色标住。拐点意味着从这里开始往大调,能得到更大的排列。
第 1 次下一排列 · 找交换对象 j：找到拐点后,再从最右边往左找第一个「大于拐点数字 3」的位置,把它拿来和拐点换。下标 3 是 4,4 大于 3,正好,j 等于 3,蓝色标住。为什么找刚好大于它的?这样换过去,增幅最小,才是紧挨着的下一个更大排列。
第 1 次下一排列 · 交换 i 与 j：把拐点 i 等于 2 的 3,和 j 等于 3 的 4 交换。1234 就变成了 1243。现在前面变大了一点,但拐点后面那一段还得处理:交换完拐点后面可能不是最小顺序,要再收拾一下。
第 1 次下一排列 · 反转后缀得 1243：最后把拐点后面那一段整体反转,让后缀尽量小。这次拐点在下标 2,后缀只有下标 3 一位,反转以后还是它自己,所以结果就是 1243。这就是第 1 个最小妙数。右边面板记上:已求到第 1 个。接着求第 2 个。
第 2 次下一排列 · 找拐点 i：在 1243 上求下一个排列。还是从右往左找拐点。下标 2 是 4,它右邻是 3,4 大于 3,不是拐点,标红跳过;再看下标 1 的 2,右邻是 4,2 小于 4,拐点就是它,i 等于 1,绿色标住。
第 2 次下一排列 · 找交换对象 j：再从最右往左找第一个大于拐点数字 2 的位置。下标 3 是 3,3 大于 2,就是它,j 等于 3,蓝色标住。注意后缀 43 是递减的,从右边第一个大于 2 的必然是恰好比 2 大一点的那个,换过去增幅最小。
第 2 次下一排列 · 交换 i 与 j：把拐点下标 1 的 2 和下标 3 的 3 交换,1243 变成 1342。这时拐点后面是下标 2 和 3 的 4、2,还是从大到小排的,不是最小,得反转一下才是真正的下一个排列。
第 2 次下一排列 · 反转后缀得 1324：把拐点后面下标 2 到 3 的 42 整体反转成 24,1342 就变成了 1324。这一步很关键:反转前是 1342,直接用会跳过好几个更小的妙数;反转后的 1324 才是紧挨着 1243 的下一个。已求到第 2 个,再求第 3 个。
第 3 次下一排列 · 找拐点 i：在 1324 上求最后一次下一排列。从右往左找拐点:下标 2 是 2,右邻下标 3 是 4,2 小于 4,拐点立刻就是它,i 等于 2,绿色标住。这次拐点靠得很右,后面处理会很轻。
第 3 次下一排列 · 找交换对象 j：从最右往左找第一个大于拐点数字 2 的位置。下标 3 是 4,4 大于 2,就是它,j 等于 3,蓝色标住。拐点后面只有这一位,待会儿交换完基本就成了。
第 3 次下一排列 · 得目标 1342：把拐点下标 2 的 2 和下标 3 的 4 交换,1324 变成 1342。拐点后面只剩一位,反转它还是自己,所以直接就是结果。第 3 个最小妙数就是 1342,这正是我们要够到的目标串。第一步大功告成。
第二步开始 · 把 1234 挪成 1342：第二步换个目标记法。上面重新摆回原串 1234,右边面板改记第二步:目标串是 1342,已经对齐的前缀、以及累计交换了几次。规则是每次只能交换相邻两位。我们从左到右,一位一位把当前串对齐成目标,顺手把交换次数加起来。
对齐第 0 位 · 目标要 1：看目标第 0 位,要的是 1。当前串下标 0 正好就是 1,不用动,零次交换。绿色标住下标 0,它已经对齐好了。前缀「1」锁定,往后这一位不再碰。看第 1 位。
对齐第 1 位 · 目标要 3：目标第 1 位要的是 3。在当前串 1234 里,3 待在下标 2,可它该去下标 1。绿色标住这个 3,红色标下标 1,那是它的目的地。相邻交换只能一步步挪,所以要把 3 和它左边的 2 交换,往左顶一格。
交换 · 3 挪到下标 1：交换下标 1 和 2 的 2 和 3,当前串从 1234 变成 1324。3 顺利落到下标 1,和目标对上了。交换次数从 0 加到 1。绿色标住就位的 3。现在前缀「13」都对齐了,看第 2 位。
对齐第 2 位 · 目标要 4：目标第 2 位要的是 4。当前串 1324 里,4 待在下标 3,它该去下标 2。绿色标住这个 4,红色标下标 2 是目的地。同样用相邻交换,把 4 和它左边的 2 换一下,往左顶一格。
交换 · 4 挪到下标 2：交换下标 2 和 3 的 2 和 4,当前串从 1324 变成 1342。4 落到下标 2,对上目标。交换次数从 1 加到 2。绿色标住就位的 4。此时前缀「134」都对齐了,只剩最后一位。
对齐第 3 位 · 目标要 2：看目标最后一位,要的是 2。当前串 1342 的下标 3 已经是 2,自动就位,不用再换。绿色标住它。到这里当前串已经完全等于目标串 1342,交换次数停在 2。为什么最后一位总能自动对上?前三位都对齐了,剩下的那位没得选,一定也对。
完成 · 最小交换次数 = 2：收尾。当前串已经完全变成目标 1342,一路数下来:对齐 3 用了 1 次交换,对齐 4 又用了 1 次,一共 2 次。这就是把 1234 变成第 3 个最小妙数所需的最少相邻交换次数。整个过程分两步:先用下一个排列求出目标,再用冒泡对齐数出代价。
复核 · 交换次数等于逆序对数：再从另一个角度复核一遍。目标串 1342 的每一位,分别来自原串的下标 0、2、3、1。把这串下标 0、2、3、1 看成一个排列,数它有几对「前面的比后面的大」的逆序对:2 比 1 大是一对,3 比 1 大又是一对,一共 2 对。逆序对数恰好等于相邻交换的最小次数,这也是参考代码直接数逆序对的道理。
边界:00123 含前导零仍参与排列(答案 1);11112 里 2 跨 4 个 1 需 4 次;本节 1234、k=3 得目标 1342、答案 2。
面试重点:下一排列每次给紧邻的下一个更大排列,做 k 次即第 k 个妙数;相邻交换每次消一个逆序对、下界即逆序对数且可达;重复数字靠位置桶按出现顺序取以避免多造逆序对。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def getMinSwaps(self, num: str, k: int) -> int: def next_permutation(nums: List[str]) -> bool: n = len(nums) i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i < 0: return False j = n - 1 while j >= 0 and nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] nums[i + 1 : n] = nums[i + 1 : n][::-1] return True s = list(num) for _ in range(k): next_permutation(s) d = [[] for _ in range(10)] idx = [0] * 10 n = len(s) for i, c in enumerate(num): j = ord(c) - ord("0") d[j].append(i) arr = [0] * n for i, c in enumerate(s): j = ord(c) - ord("0") arr[i] = d[j][idx[j]] idx[j] += 1 return sum(arr[j] > arr[i] for i in range(n) for j in range(i))复杂度
- 时间：O(k·n + n²)，n 是数字位数,k 是题目给的次数。第一步做 k 次下一个排列,每次最多扫一遍串,是 O(k·n);第二步数逆序对用的是双重循环,两两比较,是 O(n²)。两段相加就是 O(k·n + n²)。数逆序对若换成树状数组可以降到 O(n log n),但参考解用的是直观的双重循环
- 空间：O(n)，按峰值算。额外开了 10 个桶合起来存 n 个下标、一个长度为 n 的位置数组、还有目标字符数组,都是和 n 同阶的,没有更大的结构。所以额外空间是线性的 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么连做 k 次「下一个排列」就能得到第 k 个最小妙数?
追问为什么相邻交换的最少次数正好等于逆序对数?
追问数字串里有重复数字时,怎么保证配对是最优的?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
旋转盒子
LeetCode 1861 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题