386. 字典序排数
题目描述
输入一个整数 n。把 1 到 n 的所有整数当作字符串，按字典序从小到大排列。
返回排好后的整数列表。
要求时间复杂度 O(n)，除返回结果外只用 O(1) 额外空间。
示例 1
输入：n = 13 输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
解释：按字符串比较，"10" 到 "13" 都排在 "1" 之后、"2" 之前。
示例 2
输入：n = 2 输出：[1,2]
数据范围
1 <= n <= 5 * 10^4
解题思路：迭代模拟前序遍历
把 1..n 想成一棵十叉树：每个数 x 的孩子是 x0..x9。字典序就是这棵树的前序遍历。不用递归，只靠一个变量 cur 模拟：能往下走（cur * 10 ≤ n）就走到第一个孩子；否则尝试走到右兄弟 cur + 1，如果 cur 末位是 9 或 cur + 1 超过 n，就先回到父亲（cur //= 10），直到可以加 1 为止。
为什么正确
第 k 次循环开始时，cur 恰好是字典序中第 k 个数。
复杂度分析
时间 O(n)（每次回退总次数被前进次数摊还），空间 O(1)（不计输出）。
易错点
回退条件有两个：末位是 9（如 19 的下一个是 2 而不是 20），或 cur + 1 超过 n。用 while 而不是 if，因为可能连续回退多层（如 n=199 时 199 → 2）。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = []
cur = 1
for _ in range(n):
res.append(cur)
if cur * 10 <= n:
cur *= 10
else:
while cur % 10 == 9 or cur + 1 > n:
cur //= 10
cur += 1
return resclass Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
int cur = 1;
for (int k = 0; k < n; k++) {
res.add(cur);
if ((long) cur * 10 <= n) {
cur *= 10;
} else {
while (cur % 10 == 9 || cur + 1 > n) {
cur /= 10;
}
cur += 1;
}
}
return res;
}
}class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> res;
int cur = 1;
for (int k = 0; k < n; k++) {
res.push_back(cur);
if ((long long)cur * 10 <= n) {
cur *= 10;
} else {
while (cur % 10 == 9 || cur + 1 > n) {
cur /= 10;
}
cur += 1;
}
}
return res;
}
};func lexicalOrder(n int) []int {
res := []int{}
cur := 1
for k := 0; k < n; k++ {
res = append(res, cur)
if cur*10 <= n {
cur *= 10
} else {
for cur%10 == 9 || cur+1 > n {
cur /= 10
}
cur += 1
}
}
return res
}var lexicalOrder = function(n) {
const res = [];
let cur = 1;
for (let k = 0; k < n; k++) {
res.push(cur);
if (cur * 10 <= n) {
cur *= 10;
} else {
while (cur % 10 === 9 || cur + 1 > n) {
cur = Math.floor(cur / 10);
}
cur += 1;
}
}
return res;
};function lexicalOrder(n: number): number[] {
const res: number[] = [];
let cur = 1;
for (let k = 0; k < n; k++) {
res.push(cur);
if (cur * 10 <= n) {
cur *= 10;
} else {
while (cur % 10 === 9 || cur + 1 > n) {
cur = Math.floor(cur / 10);
}
cur += 1;
}
}
return res;
}其他解法
两种方法都按字典树前序遍历输出：深度优先搜索用递归维护路径，主解法用乘 10、加 1、除 10 直接在数字上移动，省掉了栈。
解法 2：字典树深度优先搜索 时间 O(n)，空间 O(log n)
把 1 到 n 看成一棵十叉字典树：节点 x 的孩子是 10x 到 10x + 9。从根的孩子 1 到 9 依次出发做前序遍历，访问节点时把它加入答案，再按 0 到 9 的顺序递归孩子，遇到超过 n 的节点就停止。前序遍历的顺序就是字典序。
直接体现“字典序 = 字典树前序遍历”，最容易理解和证明。需要递归栈，深度为数字位数 O(log n)；主解法把这次遍历改写成迭代，额外空间 O(1)。
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = []
def dfs(x):
if x > n:
return
res.append(x)
for d in range(10):
if x * 10 + d > n:
break
dfs(x * 10 + d)
for x in range(1, 10):
dfs(x)
return resclass Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> lexicalOrder(int n) {
for (int x = 1; x <= 9; x++) dfs(x, n);
return res;
}
private void dfs(long x, int n) {
if (x > n) return;
res.add((int) x);
for (int d = 0; d < 10; d++) {
if (x * 10 + d > n) break;
dfs(x * 10 + d, n);
}
}
}class Solution {
vector<int> res;
void dfs(long long x, int n) {
if (x > n) return;
res.push_back((int)x);
for (int d = 0; d < 10; d++) {
if (x * 10 + d > n) break;
dfs(x * 10 + d, n);
}
}
public:
vector<int> lexicalOrder(int n) {
for (int x = 1; x <= 9; x++) dfs(x, n);
return res;
}
};func lexicalOrder(n int) []int {
res := []int{}
var dfs func(x int)
dfs = func(x int) {
if x > n {
return
}
res = append(res, x)
for d := 0; d < 10; d++ {
if x*10+d > n {
break
}
dfs(x*10 + d)
}
}
for x := 1; x <= 9; x++ {
dfs(x)
}
return res
}var lexicalOrder = function(n) {
const res = [];
const dfs = (x) => {
if (x > n) return;
res.push(x);
for (let d = 0; d < 10; d++) {
if (x * 10 + d > n) break;
dfs(x * 10 + d);
}
};
for (let x = 1; x <= 9; x++) dfs(x);
return res;
};function lexicalOrder(n: number): number[] {
const res: number[] = [];
const dfs = (x: number): void => {
if (x > n) return;
res.push(x);
for (let d = 0; d < 10; d++) {
if (x * 10 + d > n) break;
dfs(x * 10 + d);
}
};
for (let x = 1; x <= 9; x++) dfs(x);
return res;
}