最多K次交换构建最大数字：贪心算法实现的错误排查与问题解析

你的贪心思路的核心问题 #

先看你的测试用例：输入字符串是61892795431，K=4。我们先拆解你的算法执行过程：

1. 初始数组：[6,1,8,9,2,7,9,5,4,3,1]
2. i=0时，找到i+1到末尾的最大数是索引6的9，交换0和6（swaps=1），数组变为[9,1,8,9,2,7,6,5,4,3,1]
3. i=1时，找到i+1到末尾的最大数是索引3的9，交换1和3（swaps=2），数组变为[9,9,8,1,2,7,6,5,4,3,1]
4. i=2时，当前数8大于后面所有数，不交换
5. i=3时，找到i+1到末尾的最大数是索引5的7，交换3和5（swaps=3），数组变为[9,9,8,7,2,1,6,5,4,3,1]
6. i=4时，找到i+1到末尾的最大数是索引6的6，交换4和6（swaps=4），数组变为[9,9,8,7,6,1,2,5,4,3,1]

这就是你的代码输出99876125431，但正确输出是99876215431。问题出在：当后面存在多个相同的最大值时，你的贪心策略选择了最靠后的那个进行交换，导致后续交换无法得到更优的结果。

比如在i=0时，原数组中有两个9（索引3和6），你的findMaxInRange函数会返回最后一个9（索引6），但如果选择交换索引0和3的9，后续交换能得到更优的结果：

1. 交换0和3（swaps=1）→ [9,1,8,6,2,7,9,5,4,3,1]
2. 交换1和6（swaps=2）→ [9,9,8,6,2,7,1,5,4,3,1]
3. 交换3和5（swaps=3）→ [9,9,8,7,2,6,1,5,4,3,1]
4. 交换4和5（swaps=4）→ [9,9,8,7,6,2,1,5,4,3,1]

这就是正确输出，可见贪心算法的局部最优选择（换最后一个最大值）并没有带来全局最优。

为什么贪心会失效？ #

贪心算法的核心是每一步做局部最优选择，但在这个问题中，局部最优（当前位置换最大的数）不一定能带来全局最优——不同的交换选择会影响后续的交换可能性，尤其是当存在多个相同最大值时，选择不同的位置交换，后续的调整空间完全不同。

正确解法：回溯法（DFS） #

我们需要尝试所有可能的交换，在最多K次交换的限制下，记录最大的字符串。具体思路：

1. 对于当前位置index，遍历从index到末尾的所有位置j：
   a. 如果arr[index] < arr[j]，交换两者后递归处理index+1的位置，剩余交换次数减1。
   b. 若遇到相同的最大值，跳过重复的字符以避免冗余计算。
2. 每次交换后，更新当前记录的最大字符串。
3. 回溯时将字符交换回来，尝试其他可能的交换。

修正后的Java代码示例 #

import java.util.Arrays;

public class MaximumNumberSwap {
    private static String maxStr;

    public static String findMaximumNum(String str, int k) {
        maxStr = str;
        char[] arr = str.toCharArray();
        backtrack(arr, 0, k);
        return maxStr;
    }

    private static void backtrack(char[] arr, int index, int remainingSwaps) {
        // 更新当前记录的最大字符串
        String current = new String(arr);
        if (current.compareTo(maxStr) > 0) {
            maxStr = current;
        }

        // 终止条件：无剩余交换次数或遍历到末尾
        if (remainingSwaps == 0 || index == arr.length - 1) {
            return;
        }

        // 找到当前位置之后的最大字符
        char maxChar = arr[index];
        for (int i = index + 1; i < arr.length; i++) {
            if (arr[i] > maxChar) {
                maxChar = arr[i];
            }
        }

        // 当前字符已是最大，直接递归处理下一个位置
        if (arr[index] == maxChar) {
            backtrack(arr, index + 1, remainingSwaps);
            return;
        }

        // 遍历所有等于maxChar的位置，尝试交换并回溯
        for (int i = index + 1; i < arr.length; i++) {
            if (arr[i] == maxChar) {
                // 交换当前位置与目标位置
                swap(arr, index, i);
                // 递归处理下一个位置，剩余交换次数减1
                backtrack(arr, index + 1, remainingSwaps - 1);
                // 回溯，恢复原数组
                swap(arr, index, i);

                // 跳过重复的maxChar，避免冗余计算
                while (i + 1 < arr.length && arr[i + 1] == maxChar) {
                    i++;
                }
            }
        }
    }

    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println(findMaximumNum("61892795431", 4)); // 输出99876215431
        System.out.println(findMaximumNum("1234567", 4)); // 输出7654321
    }
}

代码解释 #

• backtrack函数是核心，负责递归尝试所有可能的交换路径：
  1. 每次递归先检查当前字符串是否为已记录的最大值，若是则更新。
  2. 若没有剩余交换次数或遍历到末尾，直接返回。
  3. 找到当前位置之后的最大字符，若当前字符已是最大，直接递归处理下一个位置。
  4. 遍历所有等于最大字符的位置，交换后递归处理下一个位置，完成后回溯恢复原数组，同时跳过重复的最大字符以提高效率。

这个方法能覆盖所有可能的交换情况，确保找到全局最优的结果，而贪心算法只能处理部分简单场景，无法应对多个最大值选择的复杂情况。

内容的提问来源于stack exchange，提问作者Vivek Kumar