难度: Medium
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13 输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2 输出：[1,2]
提示：
1 <= n <= 5 * 104
Submission
运行时间: 24 ms
内存: 22.7 MB
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
def dfs(x):
yield x
for nxt in range(x * 10, min(n + 1, (x + 1) * 10)):
yield from dfs(nxt)
return [v for i in range(1, min(n + 1, 10)) for v in dfs(i)]
Explain
解题思路是使用深度优先搜索（DFS）来按字典序生成数字。从1到9开始，每个数字可以视为树的根节点，然后对于每个节点x，其子节点可以是x*10, x*10+1, ..., x*10+9，前提是这些子节点必须小于等于n。通过递归地生成每个数字的所有可能的子数字，我们可以构建出一个按字典序排列的数字列表。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
def dfs(x):
yield x # 输出当前节点
for nxt in range(x * 10, min(n + 1, (x + 1) * 10)):
yield from dfs(nxt) # 递归进入下一层
return [v for i in range(1, min(n + 1, 10)) for v in dfs(i)] # 从1至9作为起点，进行DFS
Explore
DFS在这个问题中更为合适，因为它可以更自然地按字典序生成数字。使用DFS时，我们可以从一个数开始，深入到它的所有可能的后续数字（如从1深入到10，100等），这恰好符合字典序排列的需求。相比之下，BFS会同时处理同一层级的所有数字，需要额外的存储空间来维护这一层的所有元素，这与题目要求的O(1)额外空间不符。
在`dfs`函数中，每次递归生成新数字前，都会检查这个数字是否小于等于`n`。这通过条件`min(n + 1, (x + 1) * 10)`实现，它确保不会生成超过`n`的数字。此外，每次生成的下一个数字都是当前数字的10倍或在此基础上加上一个[0-9]的数，这样的递归保证了只有满足条件的数字才会被进一步探索。
这个表达式用来确定下一个可能的数字范围以避免超出`n`。`(x + 1) * 10`表示下一个可能的十倍数节点（例如从1到10），而`n + 1`是因为我们需要包括`n`本身（如果`n`是个十倍数）。使用`min`函数确保即使计算的下一个节点起始值超过了`n`，也只会生成到`n`为止的数字，从而避免超出范围的生成，确保了程序的健壮性和正确性。