386. 字典序排数

解题思路

题目要求按字典序返回范围 [1, n] 的所有整数，且要求时间复杂度为 O(n) 和 O(1) 额外空间。字典序即数字的字符串表示按字典顺序排列，例如 1, 10, 11, 12, 13, 2, 3, …。

我们可以使用迭代的方法模拟深度优先搜索（DFS）遍历字典序树：

1. 初始化：从数字 1 开始。
2. 生成数字：每次循环将当前数字加入结果列表。
3. 选择下一个数字：
   • 如果当前数字的 10 倍不超过 n，则下一个数字是当前数字的 10 倍（进入下一层）。
   • 否则，回溯到上一层（即当前数字除以 10），直到找到一个数字，其末尾不是 9 且加 1 后不超过 n。然后将当前数字加 1（进入同一层的下一个分支）。
   • 如果回溯到 0，说明所有数字已生成完毕，提前结束循环。

代码实现

class Solution:def lexicalOrder(self, n: int) -> List[int]:res = []cur = 1for _ in range(n):res.append(cur)if cur * 10 <= n:cur *= 10else:# 回溯直到找到可以加1的数字或回溯到0while cur % 10 == 9 or cur + 1 > n:cur //= 10if cur == 0:breakif cur == 0:breakcur += 1return res

算法分析

• 时间复杂度：O(n)，每个数字恰好生成一次。
• 空间复杂度：O(1)，除输出列表外，仅使用常数空间。

示例说明

• 输入 n=13：
  1. 初始 cur=1，加入结果 [1]，1*10=10<=13 → cur=10。
  2. cur=10，加入结果 [1,10]，10*10=100>13 → 回溯：10%10=0 且 10+1=11<=13 → cur=11。
  3. cur=11，加入结果 [1,10,11]，11*10=110>13 → 回溯：11%10=1 且 11+1=12<=13 → cur=12。
  4. cur=12，加入结果 [1,10,11,12]，12*10=120>13 → 回溯：12%10=2 且 12+1=13<=13 → cur=13。
  5. cur=13，加入结果 [1,10,11,12,13]，13*10=130>13 → 回溯：13%10=3 但 13+1>13，回溯到 1 → cur=1+1=2。
  6. 后续依次加入 2,3,...,9，最终结果为 [1,10,11,12,13,2,3,4,5,6,7,8,9]。

该算法高效地按字典序生成了所有数字，满足时间和空间复杂度要求。