用给定集合中的数字组成小于 n 的最大数，数字可以重复使用。

核心回答

按题目示例，集合中的每个元素都是一位十进制数字，允许重复使用，结果必须严格小于 n。例如 n=23121、A={2,4,9}，答案是 22999，不能按“每个数字最多使用一次”的排列题处理。

可以从高位构造：尽量保留与上界相同的前缀；某位选得更小时，后面全部填集合中的最大数字；如果当前位没有合法选择，就向左回退，把最近一个能减小的位置减小，再把后缀填满。等长无解时，考虑少一位的最大数。

下面约定 n 是非负整数，结果不允许前导零；只有集合含 0 且 0 < n 时，才允许单独返回 0。无解返回 None。如果题目只接受正整数，将返回值 0 视为无解即可。

关键思路：先处理严格小于，再维护前缀

对整数，把“小于 n”转成“不超过 n−1”，可以统一处理答案刚好等于上界的情况。例如 n=222、A={2}，不能返回 222，而应返回 22。

令新的上界为 upper=n−1，从左到右逐位构造：

1. 如果能选与当前上界数位相等的数字，先选相等，继续保持前缀约束。
2. 如果只能选更小的数字，选其中最大的。此时整个数已经小于上界，剩下各位全部填集合中的最大数字，不再受上界后缀限制。
3. 如果这一位没有合法数字，保留当前已选前缀并向左回退。在最近一个可减小的位置，换成集合中严格小于原数字的最大值，再把它右侧全部填最大数字。
4. 如果整个前缀都不能减小，等长无解。集合存在非零数字时，用最大数字重复组成少一位的数；否则只可能有单独的 0，或无解。

多位数首位不能选 0，但后面的 0 可以正常使用。选过一个数字后也不从集合中删除，因此始终允许重复取用。

Python 实现

bisect_right(...)-1 查找不超过当前数位的最大数字，bisect_left(...)-1 查找严格更小的最大数字。实现使用迭代和前缀列表，不依赖递归深度。

from bisect import bisect_left, bisect_right


def max_below(n: int, allowed) -> int | None:
    if type(n) is not int or n < 0:
        raise ValueError("n must be a nonnegative integer")
    raw = list(allowed)
    if any(type(d) is not int or not 0 <= d <= 9 for d in raw):
        raise ValueError("allowed must contain decimal digits")
    digits = sorted(set(raw))
    if n == 0 or not digits:
        return None

    upper = str(n - 1)
    length = len(upper)
    largest = str(digits[-1])
    prefix = []

    for i, char in enumerate(upper):
        limit = int(char)
        j = bisect_right(digits, limit) - 1
        if j < 0 or (i == 0 and length > 1 and digits[j] == 0):
            break
        digit = digits[j]
        prefix.append(str(digit))
        if digit < limit:
            return int("".join(prefix) + largest * (length - i - 1))
    else:
        return int("".join(prefix))

    while prefix:
        i = len(prefix) - 1
        old = int(prefix.pop())
        j = bisect_left(digits, old) - 1
        if j >= 0 and not (i == 0 and length > 1 and digits[j] == 0):
            result = "".join(prefix) + str(digits[j])
            return int(result + largest * (length - i - 1))

    if length > 1 and digits[-1] != 0:
        return int(largest * (length - 1))
    return 0 if 0 in digits else None


assert max_below(23121, [2, 4, 9]) == 22999
assert max_below(24132, [2, 4, 9]) == 22999
assert max_below(222, [2]) == 22
assert max_below(1000, [0, 1]) == 111
assert max_below(1, [0]) == 0
assert max_below(8, [9]) is None
assert max_below(0, [0]) is None
assert max_below(100, []) is None

代码中的 for ... else 表示所有数位都成功走完，没有因为无候选而 break。此时构造结果恰好等于 n−1，符合严格小于 n 的要求。

为什么回退后可以直接填最大数字

没有前导零的等长十进制数，其大小由第一个不同的数位决定。更高位的差异，后面所有数位都无法弥补。

所以，保持更长的相同前缀优于更早减小；不得不减小时，应优先在最靠右的可行位置减小，并选择该位置能用的最大较小数字。这个位置一旦减小，后缀就可以全部取最大数字。题目允许重复取数，且没有相邻关系、数位和等额外限制，因此这样的后缀一定合法。

若等长无解，任何合法的少一位正数都小于上界，而少一位的最大数又大于所有更短的正数，所以不必枚举全部短长度。

例如 n=24132，上界为 24131。先保留 24，第三位 1 没有可用数字；退回前缀的第二位，把 4 改成 2，于是得到 22，后缀全填 9，答案为 22999。

复杂度

设输入数字列表长度为 m，去重后有 d 个数字，L 为上界位数。忽略任意精度整数与十进制字符串转换的成本，预处理与数位构造共需 O(m + d log d + L log(d+1)) 时间，额外空间 O(m + d + L)。每个前缀位置最多前进、回退各一次，不会枚举所有数字组合。十进制中 d≤10，数位构造部分可以视为 O(L)。

常见追问

为什么不能当前位放不下，就直接填最大数字？

如果前缀仍与上界相等，这样可能超过上界；必须先找到一个能变小的位置。例如 24131 的前缀已是 24，第三位不能放 2 或 9，需要先退回第二位。

集合含 0 时有什么变化？

多位数的首位不能是零，其他位置可以。全是零的集合只能组成数值 0，不能用 000 冒充一个三位数。无解也不能无条件返回 0，因为 0 可能根本不在集合里。

如果数字不能重复，或还要求相邻数位不同呢？

那就不能再直接用最大数字填满后缀。需要增加已使用数字、上一位等状态，判断后缀是否存在合法完成方式；可以采用带上界约束的回溯或数位 DP，再按从大到小的顺序恢复最大解。这是另一组约束，不能直接沿用当前算法的正确性证明。

参考资料