LeetCode 1505. 最多 K 次交换相邻数位后得到的最小整数
目录
题目描述
题意分析
给定一个数字字符串
num和整数k，最多可以做 $k$ 次「交换相邻两位」的操作，问能得到的字典序最小的数字串是什么。「只能交换相邻位」这条约束决定了代价模型：把某一位从下标 $i$ 搬到下标 $j$（$j < i$），恰好需要 $i - j$ 次交换，且搬运过程中它跨过的那些位会整体右移一格、相对顺序保持不变。所以一次「远距离取数」的代价就是它当前与目标之间隔了多少个还没被取走的字符。
要求字典序最小，天然是从高位往低位逐位确定：高位小一点带来的收益，压倒后面所有位的任何差异。所以问题变成：为答案的第 $1$ 位挑一个花得起的最小数字，然后第 $2$ 位，依此类推。
数据规模是关键信号：$n \le 3 \times 10^4$，而 $k$ 最大到 $10^9$。$k$ 巨大意味着 $k$ 足够大时可以直接把整串排序成升序，所以算法不能依赖 $k$ 的大小；$n$ 三万说明 $O(n^2)$ 的 $9 \times 10^8$ 有点悬，配合「树状数组」这个标签，目标应当是 $O(10 \cdot n \log n)$。
边界要注意：数字只有 $0$ 到 $9$ 十种，同一个数字可能出现很多次；相同数字之间永远应该取最靠左的那个，因为取左边的代价严格更小而结果字符完全相同。以及 $k$ 可能在中途耗尽，此后每一位只能原样取剩余中最靠左的字符（代价为 $0$ 的那个）。
解法：贪心 + 树状数组
核心思路
暴力做法是模拟：每次在剩余字符串里找「能在 $k$ 步内移到最前面的最小数字」，找到后真的把它挪过来并删除。找一次 $O(n)$，删一次也要 $O(n)$ 的数组搬移，总代价 $O(n^2) = 9 \times 10^8$，且常数不小，在困难题的时限下不稳。瓶颈有两个：一是「找最小可达数字」扫了整个剩余串，二是「真的搬运」维护了物理数组。
第一个瓶颈好解决：数字只有十种。对每个数字 $d$ 预先存下它在原串中出现的所有下标（升序队列），那么「$d$ 的最靠左未取实例」就是队首，$O(1)$ 取得。逐位构造答案时，从 $d = 0$ 到 $9$ 依次试，第一个花得起的就是当前位的最优解——因为字典序下更小的数字压倒一切。
第二个瓶颈才是本题的核心。关键观察是：不需要真的搬运字符，只需要算出代价。设某个字符的原始下标是 $idx$（1-indexed），它此刻要被搬到答案的当前位。它需要跨过的，正是原串中位于它左侧、且尚未被取走的字符个数。已被取走的字符早就离开了它的左侧，不再构成阻碍。于是代价公式为 $cost = (idx - 1) - (\text{已取走的字符中下标} < idx \text{的个数})$。
这就把问题转成了一个可以用树状数组维护的动态前缀计数：树状数组的第 $t$ 位记 $1$ 表示原下标 $t$ 的字符已被取走，
query(idx)给出前 $idx$ 个位置中已取走的数量。取走一个字符时做一次单点加一，查询代价时做一次前缀和，都是 $O(\log n)$。于是全程的不变量是：答案已构造出 $i-1$ 位；树状数组中标记为 $1$ 的恰好是这 $i-1$ 个字符的原始下标；每个数字队列的队首是该数字剩余实例中最靠左的那个；$k$ 是剩余可用的交换次数。每一轮从 $0$ 到 $9$ 找第一个满足 $cost \le k$ 的数字，扣掉代价、追加字符、打标记、弹队首，不变量得以维持。
贪心的正确性还需要一句说明：为什么选中某个数字后，被它跨过的那些字符的相对顺序不受影响？因为相邻交换只把它一格一格往左挪，被跨过的字符各自右移一位，彼此之间的先后不变。所以后续的代价计算仍然只依赖「左侧未取字符数」这一个量，贪心的每一步都独立于历史路径。
解题步骤
- 预处理十个下标队列
pos[0..9]，把每个字符的下标（存成 $i+1$ 转 1-indexed）按出现顺序压入对应队列。用队列而非集合，是因为同一数字必须优先取最左实例——代价更小而字符相同，绝无理由取更右的；队列的先进先出正好表达这个顺序。存 1-indexed 是为了直接喂给树状数组（树状数组不能接受下标 $0$，idx & -idx为 $0$ 会死循环）。- 建一个大小为 $n$ 的树状数组，初始全 $0$，表示还没有任何字符被取走。
- 外层循环 $i$ 从 $1$ 到 $n$，每轮确定答案的第 $i$ 位。从高位到低位是字典序最小的必然要求：任何让高位变小的代价都值得付。
- 内层从 $d = 0$ 递增到 $9$，跳过空队列。递增顺序保证第一个可行的就是最小可行数字，找到即
break，不必比较后面更大的数字。- 取队首下标
idx，计算moved = bit.query(idx)、cost = idx - 1 - moved。idx - 1是原串中它左侧的字符总数，moved是其中已被取走的（含它自己？不含——它自己尚未被标记，所以query(idx)统计的都是左侧已取字符），两者相减正是当前实际要跨过的字符数，也就是相邻交换次数。- 若
cost <= k，则扣除k -= cost，把字符追加到结果，执行bit.add(idx, 1)打上已取标记，弹出队首，然后break。三个更新缺一不可：不扣 $k$ 会超预算；不打标记会让后续字符的代价被高估（把已经走掉的字符仍算作阻碍）；不弹队首会重复使用同一个字符。- 若十个数字都试完仍没有
break，说明 $k$ 已不足以移动任何数字——但这种情况不会真的发生：代价最小的候选是所有剩余字符中最靠左的那个，它的cost恰为 $0$，必然满足cost <= k。所以每轮一定能产出一位，循环 $n$ 轮后答案长度恰为 $n$。- 返回拼接好的字符串。
以
num = "4321"、k = 4走一遍：预处理：
pos[4] = [1]、pos[3] = [2]、pos[2] = [3]、pos[1] = [4]（1-indexed 下标）。树状数组全 $0$，$k = 4$。
第 1 位：试 $d = 0$ 空；$d = 1$ 队首idx = 4，moved = query(4) = 0，cost = 3，$3 \le 4$ 成立。取它：$k = 1$，答案"1"，标记位置 $4$，弹出。
第 2 位：$d = 1$ 队空；$d = 2$ 队首idx = 3，moved = query(3) = 0（位置 4 的标记不在前 3 个里），cost = 2，$2 > 1$，放弃；$d = 3$ 队首idx = 2，cost = 2 - 1 - 0 = 1，$1 \le 1$ 成立。取它：$k = 0$，答案"13"，标记位置 $2$，弹出。
第 3 位：$d = 2$ 队首idx = 3，moved = query(3) = 1（位置 2 已取），cost = 3 - 1 - 1 = 1，$1 > 0$，放弃；$d = 4$ 队首idx = 1，moved = query(1) = 0，cost = 0，成立。取它：$k = 0$，答案"134"，标记位置 $1$。
第 4 位：$d = 2$ 队首idx = 3，moved = query(3) = 2（位置 1、2 已取），cost = 3 - 1 - 2 = 0，成立。答案"1342"。
返回"1342"。第 3 位那一步最能说明树状数组的作用：数字 $2$ 原本在下标 $3$，左边有两个字符，但其中位置 $2$ 的
3已经被取走了，所以真实阻碍只剩一个，代价从 $2$ 降到 $1$。如果不做这个扣减，会误判它太贵而错过。到第 4 位时左边两个都走光了，代价降为 $0$。
代码实现
class Solution {
public String minInteger(String num, int k) {
int n = num.length();
Deque<Integer>[] pos = new Deque[10];
for (int i = 0; i < 10; i++) {
pos[i] = new ArrayDeque<>();
}
for (int i = 0; i < n; i++) {
pos[num.charAt(i) - '0'].add(i + 1);
}
Fenwick bit = new Fenwick(n);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
for (int d = 0; d <= 9; d++) {
if (pos[d].isEmpty()) {
continue;
}
int idx = pos[d].peekFirst();
int moved = bit.query(idx);
int cost = idx - 1 - moved;
if (cost <= k) {
k -= cost;
sb.append((char) ('0' + d));
bit.add(idx, 1);
pos[d].pollFirst();
break;
}
}
}
return sb.toString();
}
private static class Fenwick {
private final int[] tree;
Fenwick(int n) {
tree = new int[n + 1];
}
void add(int idx, int delta) {
while (idx < tree.length) {
tree[idx] += delta;
idx += idx & -idx;
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= idx & -idx;
}
return sum;
}
}
}
func minInteger(num string, k int) string {
n := len(num)
pos := make([][]int, 10)
for i := 0; i < n; i++ {
d := int(num[i] - '0')
pos[d] = append(pos[d], i+1)
}
bit := newFenwick(n)
res := make([]byte, 0, n)
for i := 1; i <= n; i++ {
for d := 0; d <= 9; d++ {
if len(pos[d]) == 0 {
continue
}
idx := pos[d][0]
moved := bit.query(idx)
cost := idx - 1 - moved
if cost <= k {
k -= cost
res = append(res, byte('0'+d))
bit.add(idx, 1)
pos[d] = pos[d][1:]
break
}
}
}
return string(res)
}
type Fenwick struct {
tree []int
}
func newFenwick(n int) *Fenwick {
return &Fenwick{tree: make([]int, n+1)}
}
func (f *Fenwick) add(idx int, delta int) {
for idx < len(f.tree) {
f.tree[idx] += delta
idx += idx & -idx
}
}
func (f *Fenwick) query(idx int) int {
sum := 0
for idx > 0 {
sum += f.tree[idx]
idx -= idx & -idx
}
return sum
}
复杂度分析
- 时间复杂度：$O(10 \cdot n \log n)$。外层构造 $n$ 位；每位最多试 $10$ 个数字，每次试探做一次 $O(\log n)$ 的前缀和查询；选中后再做一次 $O(\log n)$ 的单点更新和 $O(1)$ 的队列弹出。$n = 3 \times 10^4$ 时约 $10 \times 3 \times 10^4 \times 15 = 4.5 \times 10^6$ 次基本操作，非常宽裕。
- 空间复杂度：$O(n)$。十个下标队列合计存 $n$ 个下标；树状数组占 $n + 1$ 个整数；结果缓冲区 $n$ 个字符。数字种类是常数 $10$，不随输入增长。
关键点总结
- 求字典序最小/最大时，一律从最高位开始逐位贪心：高位的收益无条件压倒低位，所以每一位都取「在预算内能取到的最优字符」，取定后不再回头。
- 值域很小（这里只有十个数字）时，把「找最优候选」从扫描剩余序列改成「按值域从小到大试十次」，能把 $O(n)$ 的查找降成 $O(1)$ 的队首访问。这是值域小的题目最常见的加速点。
- 相同字符只取最左实例，是可以直接断言的贪心：结果字符相同而代价严格更小，没有任何理由取右边的。凡是「取哪个都一样但代价不同」的场景都适用。
- 不要真的搬运数据，只维护「代价所依赖的统计量」。本题把 $O(n)$ 的数组删除替换成树状数组上的一次单点加，是把模拟题转成数据结构题的典型手法；能识别「代价 = 左侧未删除元素个数」这个公式，是整道题的分水岭。
- 面试视角：面试官会分三步考。先问贪心策略（逐位取最小可达数字），再问「怎么算代价」——这里必须主动说出「要扣掉左侧已被取走的字符数」，这是唯一的难点；最后问用什么结构维护，答树状数组做动态前缀计数，并说明单次 $O(\log n)$。如果被追问「不用树状数组行不行」，可以答用线段树或分块，$n$ 很小时直接 $O(n)$ 扫也行。
易错点总结
- 代价直接用
idx - 1而不扣已取走的数量：num = "4321"、k = 4时第 3 位处数字 $2$ 的代价被算成 $2$ 而非 $1$，会跳过它选 $4$，虽然本例结果相同，但在num = "9438957234785635408"、k = 23这类长串上会持续高估代价，最终答案比最优解大。- 选中后忘记
bit.add(idx, 1)：num = "4321"、k = 4时第 4 位算出的cost仍是 $2$，虽然 $k$ 已为 $0$ 也会因为没有其他候选而被迫选中，但在 $k$ 有余量的用例上会重复扣除本不该付的代价，答案偏大。- 忘记弹出队首：同一个字符会被反复选中，
num = "4321"会输出"1111"这类由重复字符构成的串。- 树状数组下标从 $0$ 开始：把
pos[d].add(i)而非i + 1，add(0, 1)中0 & -0为 $0$，idx永不前进，直接死循环。- 内层循环从 $9$ 递减到 $0$：
num = "4321"、k = 4会优先尝试大数字，第一位就选 $4$（代价 $0$），输出"4321"，正确答案是"1342"。- 找到可行数字后不
break：会继续尝试更大的数字并再次追加字符，结果串长度超过 $n$ 且内容错乱。- 判断条件写成
cost < k：num = "4321"、k = 3时第一位数字 $1$ 的代价恰为 $3$，用严格小于会被拒绝，输出"3421"之类，正确答案是"1432"。- 同一数字取队列中任意实例而非最左：
num = "11" + "0"形式的串上会付出多余代价，num = "110"、k = 2若取第二个 $1$ 会浪费一次交换，导致 $0$ 无法前移，输出"101"，正确答案是"011"。k用int但中途累减为负后继续比较：本题cost <= k只在非负时通过，k不会变负；真正的错误是把k -= cost写在判断之前，num = "4321"、k = 0时第一位就把 $k$ 扣成 $-3$，后续所有候选都不可行，循环空转产出空串。query(idx)写成query(idx - 1)：位置idx自身尚未被标记，两种写法在本题等价；但若把标记提前到判断之前再用query(idx)，会把自己算进阻碍里，代价整体多 $1$，num = "4321"、k = 4第一位就会拒绝数字 $1$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 402. 移掉 K 位数字 | 中等 | 同为逐位构造字典序最小，但操作是删除而非交换，用单调栈而非代价计算 |
| 670. 最大交换 | 中等 | 只允许一次任意位置交换，从右往左记最大数字位置即可，无需预算管理 |
| 316. 去除重复字母 | 中等 | 逐位贪心加单调栈，额外约束是每个字符恰好保留一次，需后缀计数判断可弹性 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 树状数组做动态前缀计数的另一形态，统计的是逆序对而非已删除元素 |
| 31. 下一个排列 | 中等 | 同样在数位序列上找字典序最近的目标，靠找降序拐点后局部交换与反转 |
| 321. 拼接最大数 | 困难 | 从两串各取若干位拼接最大，需枚举分配再逐段单调栈取最优并合并 |
| 1081. 不同字符的最小子序列 | 中等 | 与 316 同构，考的是逐位取最小时如何保证后续仍有解 |
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 相邻交换排序所需的最少次数就是逆序对数，与本题的代价模型同源 |