LeetCode 题解工作台
最多 K 次交换相邻数位后得到的最小整数
给你一个字符串 num 和一个整数 k 。其中， num 表示一个很大的整数，字符串中的每个字符依次对应整数上的各个 数位 。 你可以交换这个整数相邻数位的数字 最多 k 次。 请你返回你能得到的最小整数，并以字符串形式返回。 示例 1： 输入： num = "4321", k = 4 输出： "1…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作： 1. 单点更新 `update(x, delta)`： 把序列 x 位置的数加上一个值 delta；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个字符串 num 和一个整数 k 。其中，num 表示一个很大的整数，字符串中的每个字符依次对应整数上的各个 数位 。
你可以交换这个整数相邻数位的数字 最多 k 次。
请你返回你能得到的最小整数，并以字符串形式返回。
示例 1：
输入：num = "4321", k = 4 输出："1342" 解释：4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。
示例 2：
输入：num = "100", k = 1 输出："010" 解释：输出可以包含前导 0 ，但输入保证不会有前导 0 。
示例 3：
输入：num = "36789", k = 1000 输出："36789" 解释：不需要做任何交换。
示例 4：
输入：num = "22", k = 22 输出："22"
示例 5：
输入：num = "9438957234785635408", k = 23 输出："0345989723478563548"
提示：
1 <= num.length <= 30000num只包含 数字 且不含有 前导 0 。1 <= k <= 10^9
解题思路
方法一：贪心算法 + 树状数组
树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：
- 单点更新
update(x, delta)： 把序列 x 位置的数加上一个值 delta； - 前缀和查询
query(x)：查询序列[1,...x]区间的区间和，即位置 x 的前缀和。
这两个操作的时间复杂度均为 。
对于本题，要想得到在 k 次交换内字典序最小整数，我们可以「贪心」地从 num 的最高位开始考虑，即希望 num 的最高位尽可能小。我们可以依次枚举 0~9，对于当前枚举到的数位 x，判断是否可以将某个位置上的 x 通过最多 k 次交换移动到最高位。由于每一次交换只能交换相邻位置的两个数字，因此将一个距离最高位为 s 的数位移动到最高位，需要 s 次交换操作。例如当 num = 97620 时，0 与最高位的距离为 4，我们可以通过 4 次交换操作把 0 移动到最高位。
这样的交换操作相当于把 0 移动到最高位，同时将 0 之前的所有数位向后移动了一位。
我们接下来考虑次高位。与最高位类似，我们选择最小的数位 x，使得它与次高位的距离不超过 k'，其中 k' 是 k 扣除最高位交换后的剩余次数。
考虑上面 num = 97620 的例子，此时我们应当选择 x=2 交换至次高位。然而我们发现，经过第一次的交换操作，2 所在的位置发生了变化！在 num 中，2 与次高位的距离为 2，而将 0 交换至最高位后，2 与次高位的距离增加了 1，变为 3。这是因为 0 从 2 的后面「转移」到了 2 的前面，使得 2 向后移动了一位。因此，x 实际所在的位置，等于 x 初始时在 num 中的位置，加上 x 后面发生交换的数位个数。这里的「x 后面发生交换的数位个数」，就可以使用树状数组进行维护。
解题思路如下：
- 用
pos[x]按照高位到低位的顺序，存放所有 x 在 num 中出现的位置； - 从高到低遍历每一个位置。对于位置 i，我们从小到大枚举交换的数位 x。
pos[x]中的首个元素即为与当前位置距离最近的 x 的位置：- 记 j 为
pos[x]中的首元素，那么num[j]（也即是 x）当前实际所在的位置，等于 j 加上 j 后面发现交换的数位个数。我们使用树状数组查询区间[j + 1, n]，那么 num[j] 与位置 i 的实际距离 dist 为：tree.query(n) - tree.query(j) + j - i。 - 如果 dist 小于等于 k，那么我们可以将 x 交换至位置 i。我们使用树状数组更新单点 j，将对应的值增加 1，表示该位置的数位发生了变换。随后更新 k 值，以及将 j 从
pos[x]中移除。
- 记 j 为
- 遍历结束后，我们就得到了答案。
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class Solution:
def minInteger(self, num: str, k: int) -> str:
pos = defaultdict(deque)
for i, v in enumerate(num, 1):
pos[int(v)].append(i)
ans = []
n = len(num)
tree = BinaryIndexedTree(n)
for i in range(1, n + 1):
for v in range(10):
q = pos[v]
if q:
j = q[0]
dist = tree.query(n) - tree.query(j) + j - i
if dist <= k:
k -= dist
q.popleft()
ans.append(str(v))
tree.update(j, 1)
break
return ''.join(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the method: naive greedy can be O(n*k), but using a BIT or Segment Tree can reduce it to O(n log n). Space complexity is mainly for the BIT or Segment Tree, roughly O(n). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask candidates to justify why moving the smallest available digit first minimizes the integer.
- question_mark
Expect them to explain handling of swaps exceeding remaining k and edge cases with leading zeros.
- question_mark
Look for awareness of data structures like BIT or Segment Tree for efficient tracking of swap costs.
常见陷阱
外企场景- error
Attempting to swap digits greedily without considering remaining k, which may exceed limits.
- error
Ignoring the impact of leading zeros on the result string.
- error
Recomputing swap counts naively, causing timeouts on large inputs.
进阶变体
外企场景- arrow_right_alt
Allow swaps between any two digits instead of only adjacent, changing the approach to direct sorting.
- arrow_right_alt
Limit k to very small numbers to emphasize careful local greedy choices rather than global movement.
- arrow_right_alt
Modify the problem to maximize the integer instead of minimizing, applying the same greedy invariant in reverse.