TikTok 指定数字组最大数：严格小于 N 的贪心回退

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练N为非负十进制字符串，可含前导零；结果为规范非负整数字符串，无法组成时返回None。
• 每个数字无限复用；结果允许单独0，多位数不得以0开头。若必须为正整数，须删除0作为最终候选的分支。
• 输入数字数组只接受0–9整数，重复数字去重；不用把长字符串整体转成整数。

解题路线

1. 同长度且不含前导零的非负十进制数，数值顺序与字典序相同。因此从左往右尽可能贴住N的前缀；一旦某位变小，后面放最大的可用数字便是该前缀下最优答案。
2. 在每一位选择不超过N该位的最大合法数字。若恰好相等，继续受上界限制；若更小，立即用最大数字填满剩余位，不必搜索所有组合。第一位要排除0，但长度为1时允许0。
3. 若某位无合法数字，当前等前缀不能延伸。回到此前最右一位，尝试改为严格更小的可用数字；成功后其余位填最大数字。优先降低最右位，能保留更长的相等前缀，因此优于降低更左的位置。
4. 如果整串恰好等于N，也进入同样回退流程，因为题目要求严格小于而非小于等于。999且只允许9时，等长没有答案，必须退为99。
5. 等长所有可回退位都失败，则只考虑长度少一位。只要存在非零数字，全部填最大数字就是此长度最大合法数，并优于任何更短数；只有0时返回0，空数字集或N=0时无解。
6. 正确性可分两层：每个相等前缀下，首个变小位取最大选择并把后缀最大化；搜索时先试变小位置靠右的前缀。长度更短只在全部等长候选失败后考虑，不会错过更优数。
7. 固定0–9字母表最多检查10个候选，每个位置前进一次、回退至多一次。代码只在确定最终答案后构建后缀，不在每次回退时重复复制完整长度字符串。

手动走一遍

N=23415，A={2,4,9}：首位2相等，第二位3只能取2，此时已有22<N的前缀，后缀999，结果22999。N=2400且A={0,2,4}：完整2400等于上界，末两位0不能降低，回到4降成2并填44，得到2244。N=1000、A={9}：等长首位失败，取999。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def largest_below(bound, digits):
    if not isinstance(bound, str) or not bound or any(c not in '0123456789' for c in bound):
        raise ValueError('bound must be an unsigned decimal string')
    if any(type(d) is not int or not 0 <= d <= 9 for d in digits):
        raise ValueError('digits must be integers from 0 through 9')
    allowed = sorted(set(digits), reverse=True)
    bound = bound.lstrip('0') or '0'
    if bound == '0' or not allowed:
        return None
    length = len(bound)
    prefix = []

    def choose(limit, index):
        return next((d for d in allowed if d <= limit and (index > 0 or length == 1 or d > 0)), None)

    for i, char in enumerate(bound):
        digit = choose(ord(char) - ord('0'), i)
        if digit is None:
            break
        prefix.append(digit)
        if digit < ord(char) - ord('0'):
            return ''.join(map(str, prefix + [allowed[0]] * (length - i - 1)))
    # Equality is forbidden. Lower the rightmost feasible prefix position.
    while prefix:
        i = len(prefix) - 1
        previous = prefix.pop()
        digit = choose(previous - 1, i)
        if digit is not None:
            return ''.join(map(str, prefix + [digit] + [allowed[0]] * (length - i - 1)))
    if length > 1 and allowed[0] > 0:
        return str(allowed[0]) * (length - 1)
    return '0' if 0 in allowed else None

复杂度

设N规范长度为L、不同数字数为D≤10，时间O(L·D)，也即固定数字域O(L)；前缀、规范化字符串和输出O(L)空间。输入数组去重另需O(|A|)时间。

易错点与追问

容易失分的边界

• 使用≤N导致返回上界本身。
• 多位数以0开头冒充等长答案。
• 只在失败位置尝试，不回退更早的相等位。
• 将每位只能使用一次的组合题混入无限复用合同。

继续深挖

• 如果每个数字有次数限制，贪心还成立吗？
• 怎样返回最大K个合法数？
• 换成任意进制哪些证明保持成立？
• 只允许正数时，N=1且A={0}应怎样返回？