重排数字X求不大于Y的最大合法数：现有解法有误求正确思路

重排数字X的数位，找出小于等于Y的最大可能数，若无法实现则返回-1，且结果不能有前导零。

• 示例1：X=2851，Y=8774，答案为8521，该数是满足条件的最大数。

我的尝试代码（Java） #

public String process(long X, long Y) {
 if(X > Y) return "-1";
 char[] arr = (""+X).toCharArray();
 Arrays.sort(arr);
 String s = new String(arr);
 s = new StringBuilder(s).reverse().toString();
 long x1 = Long.parseLong(s);
 if(x1 <= Y) return "" + x1;
 return "=1";
}

遇到的问题 #

我的思路存在问题，因为总是直接取X数位能组成的最大数进行判断，导致部分测试用例失败。比如X=12222，Y=21111时，预期答案是12222，但代码无法得到正确结果。请问正确的解决思路是什么？

正确解决思路 #

核心是逐位贪心构造+回溯验证，分步骤处理：

1. 先做长度校验 #

把X、Y转成字符串sX、sY：

• 若sX长度 < sY长度：直接返回X数位能组成的最大无前置零数（比如X=123，Y=1000，返回321）。
• 若sX长度 > sY长度：直接返回-1，因为位数更多的数肯定比Y大。
• 若长度相等：进入逐位构造逻辑。

2. 逐位确定最优数字 #

从左到右每一位，优先尝试当前可选的最大数字，同时保证后续能构造出合法数：

• 对当前位置，先统计剩余可用的数字（用数组或哈希表记录计数）。
• 从大到小遍历可选数字：
  • 如果当前数字 < sY对应位的数字：选这个数字，剩下的所有数字按降序拼接在后面，直接返回结果（因为后面不管怎么排，整体数都比Y小，取最大排列即可）。
  • 如果当前数字 == sY对应位的数字：选这个数字，减少该数字的可用计数，递归处理下一位。如果后续能构造出合法数，就返回最终结果；如果不行，回溯（恢复计数），尝试下一个更小的数字。
  • 如果当前数字 > sY对应位的数字：跳过，尝试更小的数字。
• 如果所有数字都试过都无法构造，返回-1。

3. 特殊情况处理 #

• 禁止前导零：第一位不能选0（除非X本身就是0，此时Y>=0则返回0）。
• 若X全是0：只要Y>=0就返回0，否则返回-1。

针对测试用例的说明 #

拿X=12222，Y=21111举例：
sX和sY长度都是5，第一位尝试最大数字2，和sY第一位相等。选2后，剩余数字是[1,2,2,2]，第二位需要选<=1的数字，只能选1。选1后剩余数字是[2,2,2]，第三位需要选<=1的数字，但剩下的都是2，无法满足，所以回溯。回到第一位，尝试下一个数字1，1 < 2，直接选1，剩下的数字按降序拼接成2222，最终得到12222，符合要求。

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