LeetCode 剑指 Offer 17. 打印从1到最大的n位数
目录
题目描述
题意分析
给一个正整数
n，要按从小到大的顺序列出 1 到「最大的n位数」之间的每一个整数。n位数里最大的那个是由n个 9 拼成的，也就是 $10^n - 1$；n为 1 时是 9，为 2 时是 99，以此类推。题面上有两个容易被忽略的细节。第一，起点是 1 不是 0，最终列表长度恰好等于那个最大值本身。第二，虽然题目名字里写着「打印」，但提交接口要求的是返回一个整数数组，真正往控制台输出反而不符合签名——这一点决定了后面用什么数据类型承载结果。
边界方面，
n至少为 1，所以结果不会是空数组；n增大时结果规模按十倍膨胀，判题环境限定的n保证了数组能放进内存，但也意味着这个规模本身就是耗时的下限。另外，「最大的n位数」这个上界如果用整数存放，n稍大就会越出 32 位范围，这是原书面试题真正想考的地方。
解法：整数上界 + 顺序填充
核心思路
问题关键： 在当前在线题的
int[]返回契约下，答案必须显式包含1到10^n - 1，仅输出这些数就需要 $\Theta(10^n)$ 时间和空间，因此没有必要设计更复杂的数据结构。用整数循环计算
10^n，结果数组长度就是10^n - 1；下标i存放数字i + 1，自然满足升序和不含 0 的要求。使用整数乘法而不是Math.pow，可避免浮点转换和边界舍入。正确性： 数组下标从 0 到
limit - 2，写入值从 1 到limit - 1，恰好一一覆盖所有不超过n位的正整数，并且严格递增。面试中的大数追问： 原版《剑指 Offer》允许
n很大，此时10^n、单个数字以及结果数组长度都可能超出整数和内存范围，int[]这个接口本身就无法表达答案。应改为字符数组模拟加一，或 DFS 枚举每一位并以字符串/流式方式输出；不能只把int换成long。
解题步骤
- 令
limit = 1，连续乘 10 共n次，得到10^n。- 创建长度为
limit - 1的结果数组。- 对每个下标
i写入i + 1。- 返回结果。
口述示例：
n = 2时limit = 100，创建长度 99 的数组，依次填入 1 到 99。约束边界： 这份实现严格依赖在线题保证结果能由
int[]容纳。若n = 10，不仅上界超过 32 位，十亿级以上结果也不可能正常整体返回，应切换到大数流式方案。
代码实现
class Solution {
public int[] printNumbers(int n) {
int limit = 1;
for (int i = 0; i < n; i++) {
limit *= 10;
}
int[] result = new int[limit - 1];
for (int i = 0; i < result.length; i++) {
result[i] = i + 1;
}
return result;
}
}
func printNumbers(n int) []int {
limit := 1
for i := 0; i < n; i++ {
limit *= 10
}
result := make([]int, limit-1)
for i := range result {
result[i] = i + 1
}
return result
}
复杂度分析
- 时间复杂度：$O(10^n)$，每个输出数字必须写入一次。
- 空间复杂度：$O(1)$ 额外空间；返回数组占 $O(10^n)$。
关键点总结
- 当前题的返回类型决定了最简单的顺序填充就是最优量级。
- 用整数循环计算十的幂，避免不必要的浮点运算。
- 起点是 1，数组长度和最大值都为
10^n - 1。- 大数版本不是改用 64 位即可解决，还必须改变数字表示和输出方式。
易错点总结
- 把 0 放入结果：题目要求从 1 开始。
- 数组长度开成
limit或循环写到i <= result.length：会多一个元素或越界。- 使用
Math.pow后直接强转：引入没有必要的浮点精度风险。- 面对大
n仍整体创建整数数组：即使上界类型不溢出，也会因输出规模耗尽内存。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 66. 加一 | 简单 | 大数版本的核心子过程：按位加一并处理进位与整体进位扩容 |
| 415. 字符串相加 | 简单 | 不借助内置大数类型做十进制加法，练的是逐位对齐与进位管理 |
| 43. 字符串相乘 | 中等 | 大数乘法，需要处理下标错位累加与结果前导零 |
| 2. 两数相加 | 中等 | 把大数按位存进链表做加法，进位逻辑相同但载体不同 |
| 46. 全排列 | 中等 | 与大数版本的回溯写法同构，都是逐位枚举后在叶子处收集结果 |
| 17. 电话号码的字母组合 | 中等 | 固定层数的逐位枚举模板，可对照「每层十个候选」的递归结构 |