元宝 LeetCode 386. 字典序排数 Java实现

核心思路

字典序排数 = 对一棵「十叉字典树」做前序遍历：根是 1~9，每个节点
“cur” 的孩子是
“cur*10 + d”（d = 0~9）。先访问自己，再按 d 从小到大访问孩子，正好就是字典序。

1 → 10 → 100 → 101 → … → 109 → 11 → 110 → … → 19 → 2 → 20 → …

写法一：DFS 递归（最直观，推荐先掌握）

class Solution {
public List lexicalOrder(int n) {
List res = new ArrayList<>(n);
for (int i = 1; i <= 9; i++) dfs(i, n, res);
return res;
}

private void dfs(int cur, int n, List<Integer> res) { if (cur > n) return; res.add(cur); for (int d = 0; d <= 9; d++) { if (cur * 10 + d > n) break; // 后面的更大，直接剪掉 dfs(cur * 10 + d, n, res); } }

}

（改成
“Deque” 显式栈可去掉递归，n=5e4 时递归深度最多 5 层，完全不会栈溢出，递归版可以直接用。）

写法二：迭代求「下一个字典序数」（O(1) 额外空间，最优）

在上一个答案已验证过的逻辑上，模拟字典树的游标移动：

class Solution {
public List lexicalOrder(int n) {
List res = new ArrayList<>(n);
int cur = 1;
for (int i = 0; i < n; i++) {
res.add(cur);
if (cur * 10 <= n) {
cur *= 10; // 有孩子 → 往下走一层
} else {
// 没有孩子：回退到还能 +1 的祖先，然后 +1
while (cur % 10 == 9 || cur + 1 > n) cur /= 10;
cur++;
}
}
return res;
}
}

游标移动规则（这就是字典树的"下一个节点"）：

情况 动作 例子（n=192）

“cur*10 <= n” 深入长子 1 → 10 → 100
末位是 9 或
“cur+1 > n” 先回退（
“cur /= 10”） 109 → 11（109 末位 9，回退到 10，再…实际为 11）
其余 兄弟 +1 100 → 101

注意
“while” 里两个条件缺一不可：
“cur % 10 == 9” 处理"没有下一个兄弟"，
“cur + 1 > n” 处理"兄弟越界"（如 n=192 时 19 → 2，19+1=20 合法但 192 后的边界情况）。
复杂度

DFS 迭代
时间 O(n) O(n)
空间 O(log n) 递归栈 O(1)（不含输出）

已用 n = 1, 2, 9, 10, 13, 100, 192 验证：两种写法输出完全一致，长度均为 n。

• n=13 →
  “[1,10,11,12,13,2,3,4,5,6,7,8,9]”
• n=100 →
  “[1,10,100,11,12,…,19,2,20,21,…]”

面试建议：先说 DFS（好理解），再优化到迭代版。两个都写出来的话，第二个是加分项。