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

约 6 分钟
文章信息 9 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 字节 阿里 微软 百度
标签
数组 字符串 动态规划 数学 二分查找

题目描述

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

image-20260928223600726

image-20260928223600727

题意分析

digits 中的数字互不相同、已经升序排列，并且都在 1 到 9 之间。每个数字可以重复使用，要求统计能组成多少个不超过 n 的正整数。

由于没有 0，不需要处理前导零。设 n 有 L 位、可选数字有 D 个：不足 L 位的数一定合法，恰好 L 位的数需要逐位比较，更多位的数一定超过 n。

解法：按位计数

核心思路

[!blue]

长度为 k 时，每一位都有 D 种选择，共有 $D^k$ 个数。因此先把长度 1 到 L - 1 的数量相加。

处理等长数字时，从高位向低位走，并始终让已经选定的前缀与 n 相同。两个等长整数的大小由第一个不同的数位决定：当前位选得比 n[i] 小，整个数就一定更小，剩下的 L - i - 1 位可以任意填，贡献 $D^{L-i-1}$；当前位选得更大则不合法。

只有选中与 n[i] 相同的数字，才需要继续比较下一位。如果集合中没有这个数字，更小的分支已经计数，更大的分支都不合法，可以直接结束。若所有位都能相等，说明 n 本身也能组成，最后再加 1。

每个小于 n 的等长数字都有唯一的“首次变小位置”，所以逐位累加既不会漏计，也不会重复。

解题步骤

  1. 将 n 转成字符串，得到位数 L；预计算 power[i] = D^i。power[0] = 1 表示后面没有数位时，当前选择仍对应一个数。
  2. 累加 power[1] 到 power[L - 1]，计入所有位数更短的数。
  3. 从左到右扫描 n。在第 i 位枚举可选数字，每遇到一个小于 n[i] 的数字，就加上 power[L - i - 1]。
  4. 用 equal 记录能否选择 n[i]。数字已经升序，遇到更大的候选值可以停止内层枚举；若 equal 仍为假，返回当前答案。
  5. 全部数位匹配成功后，返回 ans + 1。

代码实现

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 的字符串表示和幂表。

关键点总结

[!green]

  • 按位数拆分后，只有与 n 等长的部分需要受上限约束。
  • 逐位过程只延续相等前缀；一旦选小，整段后缀直接用幂表计数。
  • 小于 n 的数按首次变小的位置归类，等于 n 的情况单独补上。

易错点总结

[!yellow]

  • 自由计数只到 L - 1 位；长度 L 必须逐位比较，否则会把大于 n 的数也算进去。
  • 当前位已经选定，剩余位数是 L - i - 1；最后一位选小后应当贡献 power[0] = 1。
  • 无法延续相等前缀时要结束整个过程，继续处理后续位就会为不存在的前缀计数。
  • 当 n 比所有可选数字都小时，答案自然为 0；全部位匹配成功时则必须计入 n 本身。

相似题目

题目 难度 关联与区别
357. 统计各位数字都不同的数字个数 中等 同样逐数位计数，本题限制可用数字集合，原题限制数码不能重复。
233. 数字 1 的个数 困难 同样利用高位前缀对候选分块，本题计合法整数个数，原题累计数码出现次数。
补充题 162. 指定数字组成的小于 N 的最大整数 中等 都从高位维持与 N 相同的前缀，首次选更小数字后处理后缀；本题计数，补充题求最大可行值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/18503187
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！