LeetCode 386. 字典序排数
题目描述
题意分析
将
1到n的所有整数，按照它们的十进制字符串字典序排列并返回，每个整数恰好出现一次。字典序逐位比较，公共前缀完全相同时，较短的字符串排在较长字符串之前，与按数值大小排序不同。题目要求线性时间、常数额外空间，不计必须返回的结果列表。因此不能先生成全部字符串再排序，也不能用随数字位数增长的递归栈保存遍历过程。
解法：十叉树先序迭代
核心思路
[!blue]
把整数的十进制前缀看作一棵不需要实际创建的树：最上层是首位
1到9，前缀cur的孩子依次为cur * 10到cur * 10 + 9，只保留不超过n的节点。字典序要求先输出前缀本身，再按末位大小访问它的各个子树，正好是这棵前缀树的先序遍历。输出
cur后，如果cur * 10 <= n，还有合法的第一个孩子，就应该先沿当前前缀向下进入它，因为整棵当前前缀子树都排在下一个兄弟之前。代码用等价条件cur <= n / 10判断，再做乘法。没有孩子时，先尝试同层的下一个兄弟。只有末位不是
9，且cur + 1 <= n时，加一才会得到合法兄弟；末位为9时直接加一会进位到另一个前缀，跳过先序遍历需要先处理的祖先兄弟，不能直接这样移动。如果当前层没有合法兄弟，就用整数除以十返回父前缀，再检查父层是否有下一位兄弟。这个过程可能需要连续退回多层，所以必须使用循环。找到可右移的层后再加一，就得到当前子树之后的第一个合法节点。数字本身携带全部前缀信息，因此向上返回不需要额外的栈。
外层固定输出
n次，每次按上述规则得到下一个字典序节点。最后一个输出完成后，代码仍可能计算一个已无须使用的后继，但外层计数已经结束，不会再次把它加入答案；不能只靠cur <= n控制整次遍历，否则回退后的值可能再次落入已访问范围。
解题步骤
- 创建结果列表，令
cur = 1，外层循环共执行n次。- 每轮先把当前数字加入结果。
- 若
cur <= n / 10，令cur *= 10，进入当前前缀的第一个孩子。- 否则，只要末位为
9或下一兄弟会超过n，就连续执行cur /= 10回退到上一层。- 找到存在合法兄弟的层后执行
cur++，下一轮继续输出，直到累计输出n个数。
代码实现
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>(n);
int cur = 1;
for (int i = 0; i < n; i++) {
res.add(cur);
// 前缀的孩子比下一个兄弟更早出现，有合法孩子就先下探。
if (cur <= n / 10) {
cur *= 10;
} else {
// 当前分支结束后可能要连续退出多层，直到找到合法兄弟。
while (cur % 10 == 9 || cur + 1 > n) {
cur /= 10;
}
cur++;
}
}
return res;
}
}
func lexicalOrder(n int) []int {
res := make([]int, 0, n)
cur := 1
for i := 0; i < n; i++ {
res = append(res, cur)
// 前缀的孩子比下一个兄弟更早出现，有合法孩子就先下探。
if cur <= n/10 {
cur *= 10
} else {
// 当前分支结束后可能要连续退出多层，直到找到合法兄弟。
for cur%10 == 9 || cur+1 > n {
cur /= 10
}
cur++
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$。每个整数输出一次，下探和回退对应前缀树边的访问；整次遍历中每条相关边只需常数次移动，连续回退的累计代价仍为线性。
- 空间复杂度：$O(1)$，不计返回结果，只保留当前数字和循环下标，没有创建前缀树、字符串数组或递归栈。
关键点总结
[!green]
- 字典序等价于数字前缀树的先序：先当前前缀，再它的孩子，最后才是兄弟。
- 乘十进入第一个孩子，除十返回父前缀，确认合法后加一进入兄弟。
- 末位为九与超过上界都会使本层没有下一兄弟，需要继续向上寻找。
- 固定输出数量保证最后一棵前缀子树处理完后正常结束。
易错点总结
[!yellow]
- 输出当前前缀后直接加一，会跳过所有以它开头的更长数字；应优先检查孩子。
- 只检查末位是否为九，可能生成超过上界的兄弟；只检查上界，又可能跨前缀错误进位。
- 用一次
if代替连续回退，可能在父层仍没有兄弟时错误停下。- 下探判断写成严格小于，会漏掉第一个孩子恰好等于上界的情况。
- 使用当前值是否小于上界作为总循环条件，不能保证所有数字恰好输出一次；应以输出数量控制终止。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 440. 字典序的第K小数字 | 困难 | 数字前缀形成隐式十叉树，本题按先序枚举全部节点，原题按前缀子树大小跳过整块找到第k个。 |
| 208. 实现 Trie (前缀树) | 中等 | 同样按前缀组织字典序，本题节点由数值规则隐式生成，不需要显式插入字符串。 |