LeetCode 902. 最大为 N 的数字组合

2026-09-08 HGNULB 约 6 分钟

文章信息 9 个分类 5 个标签

分类

LeetCode CodeTop 困难未解决 10-20 字节跳动微软阿里巴巴百度

题目描述

✅ 902. 最大为 N 的数字组合

题意分析

给定一个升序排列、每项都是单个数字字符的集合 digits，可以任意次重复使用集合里的数字拼成正整数，问一共能拼出多少个不超过 n 的数。

约束里有两个明确信号。第一，集合中不含 0，所以拼出来的数不可能有前导零，「用了几个数字」就等于「这个数有几位」，位数和长度可以画等号。第二，n 最大到 $10^9$，写成十进制也只有十位，可是满足条件的数本身可能有上亿个，说明答案要靠计数得到，不能靠一个个数出来。

边界集中在位数上：位数比 n 少的数天然更小，位数比 n 多的数天然更大，只有位数与 n 相同的那一批需要真正比较大小。还有一个容易被忽略的边界是 n 自己，如果它的每一位都能在集合里找到，它也是一个合法答案。

解法：按位计数

核心思路

不能从 1 枚举到 n，应按位数和前缀分类计数。设 n 的十进制长度为 L，可用数字个数为 D。由于 digits 不含 0，长度为 len < L 的合法正整数共有 $D^{len}$ 个，并且它们一定小于 n。

对长度恰好为 L 的数，从最高位开始与 n 比较。处理第 i 位时保持不变量：前 i 位与 n 完全相同，当前分支仍贴着上界。此时每个小于 n[i] 的可选数字都会让整个数立刻小于 n，剩余 L-i-1 位可任意填，因此贡献 $D^{L-i-1}$；等于 n[i] 才能继续比较下一位；大于它的选择全部非法。

如果当前位没有相等选项，贴上界的分支中断，后续无需再看；如果每一位都成功匹配，说明 n 本身合法，最后再加 1。这相当于把数位 DP 中的 tight 状态展开成一条前缀链，状态更少、代码更直接。

解题步骤

把 n 转为字符串，得到位数 L；预计算 power[i] = D^i。

累加 power[1] 到 power[L-1]，统计所有位数更短的合法数。

从最高位开始枚举 n[i]。对每个更小的候选数字，累加 power[L-i-1]。

若 digits 中存在 n[i]，继续保持相等前缀；否则立即返回当前答案。

全部 L 位都匹配成功时，返回 ans + 1，补上 n 本身。

例如 digits = ["1","3","5","7"]、n = 137：一位和两位数贡献 $4+16=20$；十位选比 3 小的 1，贡献 $4$；个位选比 7 小的 1、3、5，贡献 $3$；137 本身也能组成，再加 1，答案为 28。

代码实现

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String value = String.valueOf(n);
        int m = digits.length;
        int length = value.length();
        int[] power = new int[length];
        power[0] = 1;
        for (int i = 1; i < length; i++) {
            power[i] = power[i - 1] * m;
        }

        int ans = 0;
        for (int len = 1; len < length; len++) {
            ans += power[len];
        }

        for (int i = 0; i < length; i++) {
            char cur = value.charAt(i);
            boolean equal = false;
            for (String digit : digits) {
                char ch = digit.charAt(0);
                if (ch < cur) {
                    ans += power[length - i - 1];
                } else if (ch == cur) {
                    equal = true;
                } else {
                    break;
                }
            }
            if (!equal) {
                return ans;
            }
        }
        return ans + 1;
    }
}

import "strconv"

func atMostNGivenDigitSet(digits []string, n int) int {
    value := strconv.Itoa(n)
    m := len(digits)
    length := len(value)
    power := make([]int, length)
    power[0] = 1
    for i := 1; i < length; i++ {
        power[i] = power[i-1] * m
    }

    ans := 0
    for digitsCount := 1; digitsCount < length; digitsCount++ {
        ans += power[digitsCount]
    }

    for i := 0; i < length; i++ {
        cur := value[i]
        equal := false
        for _, digit := range digits {
            ch := digit[0]
            if ch < cur {
                ans += power[length-i-1]
            } else if ch == cur {
                equal = true
            } else {
                break
            }
        }
        if !equal {
            return ans
        }
    }
    return ans + 1
}

复杂度分析

时间复杂度：$O(L \cdot D)$，其中 L 是 n 的位数，D 是可用数字个数。幂表预计算为 $O(L)$。

空间复杂度：$O(L)$，用于保存 n 的字符串表示和幂表。

关键点总结

先统计所有更短位数，再只处理与 n 等长的数字，两部分互不重叠。

等长数字按首个小于 n 的位置分类；一旦变小，后续位可以自由选择。

相等前缀无法延续时必须立即结束，不能继续统计不存在的前缀分支。

n 全部匹配时要额外加 1；允许数字 0 的变体则需要处理前导零，宜改用完整数位 DP。

易错点总结

更短位数只统计到 L - 1；把长度 L 也自由计数会与逐位比较重复。

第 i 位选小后只剩 L - i - 1 位，幂指数多写 1 会成倍多算。

某位没有相等数字时应结束整个逐位过程，而不是只跳出内层循环。

全部位都相等时别漏掉 n 本身。

推导依赖 digits 已升序且不含 0；若条件变化，提前 break 和无前导零假设都不再成立。

相似题目

题目	难度	考察点
60. 排列序列	困难	逐位定位第 k 个排列
233. 数字 1 的个数	困难	按位统计单个数字出现次数
357. 统计各位数字都不同的数字个数	中等	无上界约束的纯排列计数
1012. 至少有 1 位重复的数字	困难	上界加数字互异的双重限制