求X的最大排列使其≤Y：在线测评算法问题求解

给定两个正整数X和Y，找出X的最大排列，使其小于等于Y。返回满足条件的最大排列整数；若不存在这样的排列，返回-1。

示例：

• 输入：X = 123, Y = 321 → 输出：321
• 输入：X = 1733, Y = 3311 → 输出：3173
• 输入：X = 999, Y = 111 → 输出：-1

错误思路分析 #

你之前的贪心思路错误在于：只考虑当前位选≤Y对应位的最大数字，但没有验证后续位能否组成合法的数。比如示例2中，前两位选3、3后，剩下的数字是1、7，无论怎么排列都会得到3317或3371，都大于3311，导致整个路径无效，但此时还有更优的路径（第一位3，第二位1，剩下的降序排列为73），你的贪心没考虑回溯退选。

递归思路栈溢出是因为没有剪枝，递归深度等于数字位数时（比如10位数字）就容易触发栈溢出，需要改成带剪枝的回溯或迭代实现。

正确解题思路 #

核心是带回溯的贪心策略，分情况处理，同时利用数字频率统计来高效判断可选数字：

1. 预处理与长度判断 #

• 将X、Y转为字符串x_str、y_str，统计X的数字频率（用长度为10的数组count，count[d]表示数字d出现的次数）。
• 如果len(x_str) > len(y_str)：直接返回-1（X的排列位数更多，不可能≤Y）。
• 如果len(x_str) < len(y_str)：直接返回X的数字降序排列组成的数（位数更少时，最大排列就是降序，必然≤Y）。

2. 位数相同时的逐位构建 #

从左到右逐位确定结果的每一位，每一步优先尝试更大的数字，同时验证路径可行性：

def find_max_permutation(x, y):
    x_str = str(x)
    y_str = str(y)
    n = len(x_str)
    if n > len(y_str):
        return -1
    if n < len(y_str):
        return int(''.join(sorted(x_str, reverse=True)))
    
    count = [0]*10
    for c in x_str:
        count[int(c)] += 1
    
    def backtrack(pos, tight):
        # tight=True表示前pos位都和Y的前pos位相同，当前位不能超过Y[pos]
        if pos == n:
            return ""
        res = "-1"
        # 从大到小尝试数字
        for d in range(9, -1, -1):
            if count[d] == 0:
                continue
            if tight and d > int(y_str[pos]):
                continue
            # 选当前数字
            count[d] -= 1
            new_tight = tight and (d == int(y_str[pos]))
            sub_res = backtrack(pos+1, new_tight)
            if sub_res != "-1":
                res = str(d) + sub_res
                # 找到当前位的最大可行数字，直接返回，不用继续尝试更小的
                count[d] += 1
                return res
            # 回溯，恢复计数
            count[d] += 1
        return res
    
    result = backtrack(0, True)
    return int(result) if result != "-1" else -1

关键逻辑说明 #

• tight标记：用来约束当前位是否能超过Y对应位。如果前几位都和Y完全相同（tight=True），当前位不能大于Y的当前位；如果前几位已经比Y小（tight=False），剩下的位直接降序排列即可。
• 剪枝：每一步找到可行的最大数字后立即返回，不用继续尝试更小的数字，保证效率。
• 回溯处理：当选择和Y当前位相同的数字后，若后续无法组成合法数，则恢复该数字的计数，尝试更小的数字。

示例2的执行过程 #

1. 第一位尝试3（等于Y的第一位3），count[3]变为1，进入下一位，tight=True。
2. 第二位尝试3（等于Y的第二位3），count[3]变为0，进入下一位，tight=True。
3. 第三位尝试7（大于Y的第三位1），跳过；尝试3（count为0），跳过；尝试1（等于Y的第三位1），count[1]变为0，进入第四位，tight=True。
4. 第四位只能尝试7（大于Y的第四位1），无法满足，返回-1。
5. 回溯到第三位，恢复count[1]，尝试更小的数字（0，无），返回-1。
6. 回溯到第二位，恢复count[3]，尝试比3小的最大数字1，count[1]变为0，进入下一位，tight=False（因为1<3）。
7. 剩下的数字是7、3，直接降序排列为73，拼接得到3173，返回结果。

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