元宝 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, ListInteger 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” 显式栈可去掉递归n5e4 时递归深度最多 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 的祖先然后 1while (cur % 10 9 || cur 1 n) cur / 10;cur;}}return res;}}游标移动规则这就是字典树的下一个节点情况 动作 例子n192“cur*10 n” 深入长子 1 → 10 → 100末位是 9 或“cur1 n” 先回退“cur / 10” 109 → 11109 末位 9回退到 10再…实际为 11其余 兄弟 1 100 → 101注意“while” 里两个条件缺一不可“cur % 10 9” 处理没有下一个兄弟“cur 1 n” 处理兄弟越界如 n192 时 19 → 219120 合法但 192 后的边界情况。复杂度DFS 迭代时间 O(n) O(n)空间 O(log n) 递归栈 O(1)不含输出已用 n 1, 2, 9, 10, 13, 100, 192 验证两种写法输出完全一致长度均为 n。n13 →“[1,10,11,12,13,2,3,4,5,6,7,8,9]”n100 →“[1,10,100,11,12,…,19,2,20,21,…]”面试建议先说 DFS好理解再优化到迭代版。两个都写出来的话第二个是加分项。