Python3

假设$n=1$，打印$[1,2,...,9]$
假设$n=2$，打印$[1,2,...,99]$
假设$n=3$，打印$[1,2,...,999]$
…
以此类推
最大的数字$max$与$n$之间的关系为$max=10^n-1$

根据题意，可写如下代码：

class Solution:
	def printNumbers(self, n: int) -> List[int]:
		return [num for num in range(1, 10**n)]
1
2
3

提交之后，顺利通过。

看了评论区，说这题的本意是考察大数问题。上面的写法没有考虑大数（即大于int类型能表示的最大数），但实际上List[int]已经表达了输出的数字是int类型，因此实际上不必考虑大数。

如果非要考虑大数，那本题的写法如下：（参考https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/jian-zhi-offer-17-da-yin-cong-1dao-zui-d-ngm4/）

class Solution:
    def printNumbers(self, n: int) -> List[int]:

        # 数字的全排列问题，使用深度优先搜索解决
        def dfs(index, num, digit):  # index表示当前在第几位，num表示存储数字各位上数值的列表，digit表示当前的数字共有几位
            if index == digit:  # 当前位数与digit相等，说明数字填充好了
                res.append(int(''.join(num)))
                return
            for i in range(10):  # 否则，填充下一位上的数值
                num.append(str(i))
                dfs(index + 1, num, digit)
                num.pop()

        res = []  # res用于存储待打印的整数列表

        for digit in range(1, n + 1):  # digit表示数字的位数，如数字9有1位，数字99有2位，数字999有3位等等
            for first in range(1, 10):  # 数字的首位，首位的取值范围是[1,10)
                num = [str(first)]  # num用于保存数字各位上的数值
                dfs(1, num, digit)
        
        return res  # 返回整数列表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度分析：

递归生成全排列的数量为$10^n$，因此时间复杂度为$O(10^n)$。