#386. 字典序排数

LeetCode 原题链接

#题目描述

给定一个整数 n，按照字典序返回 [1, n] 内的所有整数。

输入：n = 13
输出：[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

题目还要求算法的时间复杂度为 O(n)，并且只使用 O(1) 额外空间。

#什么是字典序？

字典序就是把数字当作字符串，按照查字典的方式比较。

例如比较 2 和 13：先比较第一个字符，"1" < "2"，所以 13 排在 2 前面。

普通数值顺序：1, 2, 3, ..., 9, 10, 11, 12, 13
字典序：      1, 10, 11, 12, 13, 2, 3, ..., 9

最直接的办法是把所有数字转成字符串后排序，但排序需要 O(n log n) 时间，不满足题目的 O(n) 要求。

#核心思路：把数字看成一棵十叉树

把 1 到 9 看作第一层节点。对于任意数字 x，它后面追加一位 0 到 9，就得到它的子节点：

1
├── 10
│   ├── 100
│   ├── 101
│   └── ...
├── 11
├── 12
└── ...

2
├── 20
├── 21
└── ...

在不超过 n 的前提下，对这棵树进行先序遍历，访问顺序恰好就是字典序：先访问当前数字，再尽量访问以它为前缀的数字，最后访问下一个兄弟分支。

我们不需要真的创建这棵树，只维护当前数字 current，通过数学运算模拟移动：

#如何找到下一个数字？

将当前数字加入答案后，分两种情况。

#情况一：可以继续向下

如果 current * 10 <= n，说明最左侧子节点存在。下一项就是 current * 10。

current = 1，n = 13
1 * 10 <= 13，所以进入子节点 10

#情况二：不能继续向下

此时应尝试下一个兄弟 current + 1。但遇到下面两种情况时，没有合法的下一个兄弟：

• 当前数字以 9 结尾，例如 19 后面不能直接变成 20，因为 20 不再属于前缀 1 的子树。
• current + 1 > n，例如 13 是本题范围内前缀 1 的最后一个节点。

这时要不断删除末尾数字，也就是回到父节点，直到可以移动到某个祖先的下一个兄弟节点。

n = 13，current = 13

13 不能向下，14 又超过 n
13 / 10 = 1        // 回到父节点
1 + 1 = 2          // 移到下一个兄弟

再看一个需要连续回退的例子：

current = 199

199 以 9 结尾：199 → 19
19 仍以 9 结尾： 19 → 1
然后移动到兄弟节点：1 → 2

#示例推演

以 n = 13 为例：

最终得到：

[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

#更容易理解的递归实现

如果优先考虑容易理解，可以直接对数字十叉树进行 DFS（深度优先搜索）。

第一层是 1 到 9。访问数字 current 后，依次尝试在它的末尾添加 0 到 9，得到它的子节点：

访问 1
├── 访问 10
├── 访问 11
├── 访问 12
└── 访问 13

然后访问 2、3、4……

#JavaScript 实现

var lexicalOrder = function (n) {
  const result = [];

  // 遍历以 current 为根的数字子树
  const dfs = (current) => {
    // 超出 [1, n] 的范围，当前节点不存在
    if (current > n) {
      return;
    }

    // 先访问当前节点，对应树的先序遍历
    result.push(current);

    // 依次访问 current 的子节点：
    // current * 10、current * 10 + 1、...、current * 10 + 9
    for (let digit = 0; digit <= 9; digit++) {
      const child = current * 10 + digit;

      // 后面的 child 只会更大，可以直接结束循环
      if (child > n) {
        break;
      }

      dfs(child);
    }
  };

  // 数字不能以 0 开头，因此第一层从 1 到 9
  for (let firstDigit = 1; firstDigit <= 9; firstDigit++) {
    if (firstDigit > n) {
      break;
    }
    dfs(firstDigit);
  }

  return result;
};

这版代码可以概括成三步：

1. 把当前数字加入结果。
2. 在末尾依次添加 0 到 9，递归访问子节点。
3. 子节点超过 n 时停止当前分支。

以 n = 13 为例，递归调用顺序为：

dfs(1)
  ├── dfs(10)
  ├── dfs(11)
  ├── dfs(12)
  └── dfs(13)
dfs(2)
dfs(3)
...
dfs(9)

递归版的时间复杂度也是 O(n)，因为每个数字只加入结果一次。递归深度等于数字的位数，所以额外空间复杂度为 O(log n)。

它更适合第一次理解这道题；理解“十叉树的先序遍历”后，再学习下面通过乘十、加一和除十模拟 DFS 的迭代版。

#满足 O(1) 额外空间的迭代实现

var lexicalOrder = function (n) {
  // 保存最终的字典序结果
  const result = [];

  // 字典序中的第一个数字一定是 1
  let current = 1;

  // [1, n] 一共有 n 个数字，因此循环固定执行 n 次
  for (let i = 0; i < n; i++) {
    // current 始终表示当前尚未加入结果的最小字典序数字
    result.push(current);

    if (current * 10 <= n) {
      // 存在子节点时，优先在末尾添加 0
      // 例如：1 -> 10、12 -> 120
      current *= 10;
    } else {
      // 无法继续向下时，准备寻找下一个兄弟节点
      //
      // 需要回退的情况：
      // 1. current 以 9 结尾，没有下一个兄弟，例如 19
      // 2. current + 1 超过 n，例如 n = 13、current = 13
      //
      // 除以 10 相当于删除末位数字，回到父节点
      while (current % 10 === 9 || current + 1 > n) {
        current = Math.floor(current / 10);
      }

      // 移动到当前节点或祖先节点的下一个兄弟
      // 例如：12 -> 13，或者 13 -> 1 -> 2
      current++;
    }
  }

  // result 的长度为 n，包含 [1, n] 内的全部数字
  return result;
};

外层循环固定执行 n 次，所以即使最后一轮计算出的“下一项”不再使用，也不会影响结果。

#代码与思路对照

current * 10 <= n
        │
        ├── 是：进入子节点 current * 10
        │
        └── 否：能否直接访问 current + 1？
                  │
                  ├── 否：不断除以 10，向父节点回退
                  │
                  └── 是：current + 1，访问兄弟节点

循环开始时，current 始终是尚未加入答案的、字典序最小的数字。每轮把它加入结果后，再按照“子节点优先，其次兄弟节点，最后回退找祖先的兄弟节点”的顺序寻找下一项，这正是树的先序遍历规则。

#正确性说明

数字 x 的所有后代都以 x 为前缀，因此在字典序中，它们一定排在 x 之后、x + 1 之前。

• 存在子节点时先执行 current *= 10，保证优先访问当前前缀下最小的数字。
• 不存在子节点时执行 current++，访问同层的下一个兄弟。
• 没有合法兄弟时不断除以 10，跳过已经访问完的子树，直到找到祖先的下一个兄弟。

每个合法数字都会作为一个树节点被访问一次，访问顺序符合先序遍历，因此结果既没有遗漏或重复，也严格满足字典序。

#复杂度分析

• 时间复杂度：O(n)。一共输出 n 个数字；每次除以 10 都是在回退一层，而遍历过程中向下和向上的总次数都是线性的。
• 额外空间复杂度：O(1)，只使用了少量变量，不需要递归栈或显式树结构。
• 返回数组本身需要 O(n) 空间，但通常不计入额外空间。

#为什么不直接排序？

const result = Array.from({ length: n }, (_, i) => i + 1);
result.sort((a, b) => String(a).localeCompare(String(b)));

这种写法直观，但排序需要 O(n log n) 次比较，每次比较还可能检查多个字符，同时会创建字符串。它适合帮助理解或快速验证答案，不是本题要求的最优解法。

#易错点

• 把字典序理解成数值大小顺序。
• 只在 current % 10 === 9 时回退，忘记处理 current + 1 > n，例如 n = 13、current = 13。
• 回退只执行一次。像 199 这样的数字可能需要连续删除多个末位，因此必须使用 while。
• 回退后忘记执行 current++，导致重复访问祖先节点。
• 使用递归 DFS 虽然容易理解，但会占用递归栈，不满足严格的 O(1) 额外空间要求。

#面试时怎么说

把整数按十进制前缀组织成一棵十叉树，字典序就是这棵树的先序遍历。维护当前数字：如果乘以 10 不超过 n，就进入最左侧子节点；否则不断删除末位，直到能访问下一个兄弟节点，再加一。整个过程不需要真正建树，每个数字访问一次，时间复杂度是 O(n)，额外空间复杂度是 O(1)。

#自测

1. 为什么 1 后面是 10，而不是 2？
2. 当 n = 13、current = 13 时，如何得到下一个数字 2？
3. 为什么 199 之后寻找下一个分支时可能需要连续回退？
4. 如果改用递归 DFS，时间和空间复杂度分别是多少？