Hard

题目描述

给你一个字符串 num，表示一个很大整数的数字，和一个整数 k。你最多可以交换这个整数中任意两个相邻的数字 k 次。

请你返回你能得到的最小整数，并且以字符串形式返回。

示例 1：

输入：num = "4321", k = 4
输出："1342"
解释：通过最多 4 次交换相邻数字的步骤如图所示，我们可以得到最小整数。

示例 2：

输入：num = "100", k = 1
输出："010"
解释：输出可以包含前导零，但输入保证不含前导零。

示例 3：

输入：num = "36789", k = 1000
输出："36789"
解释：我们可以保持原样，不进行任何交换。

约束条件：

  • 1 <= num.length <= 3 * 10^4
  • num 只包含数字且不含前导零
  • 1 <= k <= 10^9

解题思路

这道题的核心思路是贪心算法：我们希望让较小的数字尽可能出现在高位。

基本思路：

  1. 从左到右遍历每一个位置，对于当前位置，我们希望在剩余交换次数允许的范围内，找到能够移动到当前位置的最小数字。
  2. 对于位置 i，我们可以在位置 [i, i+k] 范围内寻找最小的数字，因为最多用 k 次交换可以将该范围内的任何数字移动到位置 i。
  3. 找到最小数字后，将其通过相邻交换移动到当前位置，更新剩余交换次数。

优化思路： 由于我们需要频繁地查找范围内的最小值，并且需要删除元素，可以使用以下数据结构：

  • 方法1（推荐）：使用队列存储每个数字的位置索引，贪心地从小到大处理
  • 方法2：使用线段树或树状数组来维护区间查询和单点更新

具体算法流程：

  1. 为每个数字（0-9）维护一个队列，存储该数字在原字符串中的位置
  2. 对于结果字符串的每一位，从数字0开始查找，看能否在剩余交换次数内将其移动到当前位置
  3. 选择第一个满足条件的最小数字，计算移动成本，更新交换次数
  4. 由于前面的数字被移动，后续数字的实际位置会发生变化，需要用树状数组或其他数据结构维护偏移量

代码实现

class Solution {
public:
    string minInteger(string num, int k) {
        int n = num.size();
        vector<queue<int>> pos(10);
        
        // 为每个数字建立位置队列
        for (int i = 0; i < n; i++) {
            pos[num[i] - '0'].push(i);
        }
        
        string result = "";
        vector<bool> used(n, false);
        
        for (int i = 0; i < n; i++) {
            // 尝试从最小的数字开始
            for (int digit = 0; digit <= 9; digit++) {
                if (pos[digit].empty()) continue;
                
                // 移除已使用的位置
                while (!pos[digit].empty() && used[pos[digit].front()]) {
                    pos[digit].pop();
                }
                
                if (pos[digit].empty()) continue;
                
                int idx = pos[digit].front();
                
                // 计算将这个数字移动到位置i需要的交换次数
                int swaps_needed = 0;
                for (int j = idx - 1; j >= 0; j--) {
                    if (!used[j]) swaps_needed++;
                }
                
                if (swaps_needed <= k) {
                    result += (char)('0' + digit);
                    used[idx] = true;
                    k -= swaps_needed;
                    pos[digit].pop();
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        from collections import deque
        
        n = len(num)
        pos = [deque() for _ in range(10)]
        
        # 为每个数字建立位置队列
        for i in range(n):
            pos[int(num[i])].append(i)
        
        result = ""
        used = [False] * n
        
        for i in range(n):
            # 尝试从最小的数字开始
            for digit in range(10):
                if not pos[digit]:
                    continue
                
                # 移除已使用的位置
                while pos[digit] and used[pos[digit][0]]:
                    pos[digit].popleft()
                
                if not pos[digit]:
                    continue
                
                idx = pos[digit][0]
                
                # 计算将这个数字移动到当前位置需要的交换次数
                swaps_needed = sum(1 for j in range(idx) if not used[j])
                
                if swaps_needed <= k:
                    result += str(digit)
                    used[idx] = True
                    k -= swaps_needed
                    pos[digit].popleft()
                    break
        
        return result

public class Solution {
    public string MinInteger(string num, int k) {
        int n = num.Length;
        Queue<int>[] pos = new Queue<int>[10];
        for (int i = 0; i < 10; i++) {
            pos[i] = new Queue<int>();
        }
        
        // 为每个数字建立位置队列
        for (int i = 0; i < n; i++) {
            pos[num[i] - '0'].Enqueue(i);
        }
        
        StringBuilder result = new StringBuilder();
        bool[] used = new bool[n];
        
        for (int i = 0; i < n; i++) {
            // 尝试从最小的数字开始
            for (int digit = 0; digit <= 9; digit++) {
                if (pos[digit].Count == 0) continue;
                
                // 移除已使用的位置
                while (pos[digit].Count > 0 && used[pos[digit].Peek()]) {
                    pos[digit].Dequeue();
                }
                
                if (pos[digit].Count == 0) continue;
                
                int idx = pos[digit].Peek();
                
                // 计算将这个数字移动到当前位置需要的交换次数
                int swapsNeeded = 0;
                for (int j = 0; j < idx; j++) {
                    if (!used[j]) swapsNeeded++;
                }
                
                if (swapsNeeded <= k) {
                    result.Append((char)('0' + digit));
                    used[idx] = true;
                    k -= swapsNeeded;
                    pos[digit].Dequeue();
                    break;
                }
            }
        }
        
        return result.ToString();
    }
}

var minInteger = function(num, k) {
    if (k === 0) return num;
    
    const n = num.length;
    const digits = num.split('');
    let swaps = k;
    
    for (let i = 0; i < n && swaps > 0; i++) {
        let minIdx = i;
        let minDigit = digits[i];
        
        // Find the smallest digit within swaps range
        for (let j = i + 1; j < n && j <= i + swaps; j++) {
            if (digits[j] < minDigit) {
                minDigit = digits[j];
                minIdx = j;
            }
        }
        
        // Move the smallest digit to position i
        while (minIdx > i && swaps > 0) {
            [digits[minIdx], digits[minIdx - 1]] = [digits[minIdx - 1], digits[minIdx]];
            minIdx--;
            swaps--;
        }
    }
    
    return digits.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n²) - 对于每个位置需要遍历10个数字，计算交换次数需要O(n)时间
空间复杂度O(n) - 需要存储位置队列和使用标记数组