### 题目

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

### 把数字转换成字符，然后排序，$O(n\log_{}{n})$

Colletcions.sort()排序。写一个Comparator，把数字转换成字符，然后比较。

#### 代码

class Solution {
private static final int INT_SIZE = 10;
private static int[] ca = new int[INT_SIZE];
private static int[] cb = new int[INT_SIZE];
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i <= n; i++) {
}
Collections.sort(res,new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
int pa = parse(ca,a);
int pb = parse(cb,b);
while (pa < INT_SIZE && pb < INT_SIZE) {
int x = ca[pa++];
int y = cb[pb++];
if (x < y) {
return -1;
} else if (x > y) {
return 1;
}
}
if (pa < INT_SIZE) { return 1; }    // a is longer
if (pb < INT_SIZE) { return -1; }   // b is longer
return 0;
}
});
return res;
}
private int parse(int[] c, int n) {
int pa = INT_SIZE;
while (n > 0) {
c[--pa] = n % 10;
n /= 10;
}
return pa;
}
}


### 不转化成字符，左对齐数字然后比较大小，$O(n\log_{}{n})$

2    -> 20000000000
111  -> 11100000000


1    -> 10000000000
10   -> 10000000000
100  -> 10000000000


#### 代码

class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i <= n; i++) {
}
Collections.sort(res,new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
long diff = leftAlign(a) - leftAlign(b);
if (diff < 0) {
return -1;
} else if (diff > 0) {
return 1;
} else {
return 0;
}
}
});
return res;
}
private final long STD = 10000000000L;
private long leftAlign(int n) {
long l = (long)n;
while (true) {
long next = l * 10;
if (next < STD) {
l = next;
} else {
break;
}
}
return l;
}
}


### 有限状态机逐个生成数字，$O(n)$

#### 代码

class Solution {
private static List<Integer> res = new ArrayList<>();
private static int[] board = new int[10];
public List<Integer> lexicalOrder(int n) {
res.clear();
for (int i = 1; i < 10; i++) {
int bp = -1;
for (int j = i; j <= n; j *= 10) {
board[++bp] = j+1;
}
int maxbp = bp;
while (bp > 0) {
if (board[bp] / 10 < board[bp-1]) {                         // 检查进位
if (bp < maxbp) {                                       // 最后一个计数器
if (maxbp - bp > 1 || board[maxbp] <= n) { bp++; }  // 最后一个计数器到了最大值，不再往后进一步
} else if (board[bp] <= n) {                            // 非最后一个计数器
} else {
bp--;
}
} else {                                                    // 进位
bp--;
}
}
}
return res;
}
}


### 标准DFS解法，$O(n)$

0
1 -> 10 -> 100
2    11    101
3    12    102
.    .     .
9    19    109


#### 代码

class Solution {
private static List<Integer> list = new ArrayList<>();
private static int max = 0;
public List<Integer> lexicalOrder(int n) {
list.clear();
max = n;
dfs(0);
return list;
}
private void dfs(int seed) {
for (int i = 0; i < 10; i++) {
if (seed == 0 && i == 0) { continue; } // 跳过0的情况
int num = seed + i;
if (num > max) { return; }