LeetCode 1505. 最多 K 次交换相邻数位后得到的最小整数
题目描述
题意分析
每次只能交换相邻的两个数位，在最多
k次交换内，返回能够得到的最小数字字符串。输出允许前导零，而且长度始终不变，因此比较结果大小等价于比较字典序。字典序优先比较最靠前的不同位置。可以从左到右固定答案，每次选出剩余预算能够移到当前位的最小数字，再处理后面的部分。
解法：贪心 + 树状数组
核心思路
[!blue]
已经选出的数位组成固定前缀，尚未选出的数位仍保持原来的相对顺序。把其中一个数位移到剩余串开头，必须跨过它前方的每个剩余数位，每跨过一个至少交换一次；连续向左交换也恰好能完成这些移动，所以所需代价就是它前方尚未取出的数位个数。
为数字
0..9分别保存一个原位置队列pos[d]，位置从1开始。相同数字只需考虑最早未取出的一项：它的移动代价最低。若一种操作让两个同值数位颠倒先后，它们跨越彼此时必有一次交换相同数字，这一步不改变字符串，可以省去；因此总能让同值数位按原出现顺序被选走，无需尝试更晚的同值位置。为了快速计算当前代价，用树状数组标记已取出的原位置，每取出一个就在该位置加一。对候选原位置
idx，原本前方有idx-1个数位，减去前缀中已取出的数量，得到cost = idx-1-bit.query(idx)。候选本身还没有取出，所以查询包含idx也不会多减；剩余数位的相对顺序未变，这个数量正是实际需要的相邻交换次数。每轮从
0到9尝试，找到第一个cost <= k的数字就选中。更小数字都无法在预算内到达当前位，而选一个更大的数字会让当前前缀变差，任何后缀都无法弥补。选中的数字只花费必要的最少交换，扣除代价后，后续仍是同样的最小后缀问题，所以逐位选择得到全局最优结果。选定后再从位置队列弹出队首，并在树状数组中标记该位置已取出。每轮至少能选择剩余串最左边的数字，因为它的代价为
0；即使预算已经耗尽，也能继续按剩余顺序输出，最终恰好选出全部n个数位。
解题步骤
- 扫描原字符串，把每种数字的所有原位置按递增顺序加入各自队列，使用从
1开始的下标。- 初始化全零树状数组，表示尚未取出任何位置。
- 为当前答案位置按
0..9尝试非空队列的队首，用原前缀长度减去已取出数量计算交换代价。- 遇到第一个预算可承担的候选，追加数字并扣减
k，随后弹出该位置、将树状数组对应位置加一。- 重复直到输出
n个数位，直接返回字符串，保留可能存在的前导零。
代码实现
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(10n\log(n+1))$。每个输出位置最多检查 10 个候选，每次前缀查询和选定后的单点更新都为对数时间。
- 空间复杂度：$O(n)$。十个位置队列合计保存
n个下标，树状数组和答案也各占线性空间。
关键点总结
[!green]
- 相邻交换的最少次数是候选前方仍未取出的数位数，不能直接使用不变的原下标距离。
- 同值数位按原顺序取出即可，每个数字只需考察位置队列的队首。
- 当前位能够承担的最小数字决定最优前缀，后缀无法抵消更大高位带来的劣势。
- 树状数组只标记已选位置，查询代价必须发生在标记当前候选之前。
易错点总结
[!yellow]
- 把相邻交换当成任意两位交换，会低估把远处数位移到前方的成本。
- 不扣除之前已取出的原位置，会高估后续数位前方仍需跨越的元素数量。
- 先标记候选已取出再计算代价，会把候选自身也减掉，使成本少一。
- 遇到同一个数字时选择更晚的位置，会额外跨越更早的同值数位，浪费预算。
- 将结果转换成整数会丢掉允许的前导零，也无法承载题目中的长数字字符串。
- 树状数组更新不能从下标
0开始，原字符位置应先加一。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1850. 邻位交换的最小次数 | 中等 | 同样按稳定字符匹配计算相邻交换代价，本题目标自由但预算受限，原题目标是指定后继排列。 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 树状数组的动态秩统计可复用，本题用它计算某数位前面还有多少未移走字符。 |