解法一

對於任何數字，比這個數字多一位的數字中，最小（字典序）的就是加一個 0 在後面，最大的就是加一個 9 在後面。

因此可以建構出一棵樹，並且這棵樹用 preorder traversal 遍歷的話，剛剛好會是字典序從小到大排列。這邊只列出這棵樹的前面兩層，實際上這棵樹是無限層的。

       k
    /     \
10*k ... 10*k+9

所以只需要遍歷以 1 到 9 爲根的這九棵樹就好，並且當節點大於 n 的時候可以不用遍歷下去。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
vector<int> lexicalOrder(int n) {
    vector<int> ans;
    function<void(int)> dfs = [&](int i){
        if (i > n){
            return;
        }
        ans.push_back(i);
        for (int j = 0; j <= 9; j++){
            dfs(i * 10 + j);
        }
        return;
    };
    for (int i = 1; i <= 9; i++){
        dfs(i);
    }
    return ans;
}

time complexity: $O(n)$
space complextiy: $O(\log n)$
空間複雜度是 $\log n$ 的原因是這棵樹每多一層，數字會變成 10 倍，所以最多只會有 $\log_{10} n$ 那麼多層。

解法二

第二個解法是我覺得比較直觀的方法，也就是直接從字典序下手。

假設現在想要知道數字 k 的下一個數字（字典序的排列），最小的就會是 10k ，但如果 10k 大於 n 的話該怎麼辦呢？

那麼最小的就是 k+1，但如果 k+1 大於 n 的話或是 k+1 需要進位該怎麼辦呢？

這時候最小的數字，就是把 k 減少位數，直到末位不爲 9，然後再加 1。

末位爲 9 的時候再加上 1，其實等於把倒數第二位加 1，然後末位變成 0。但是這個時候把末位的 0 直接去掉，可以得到字典序更小的數字，因此需要不斷地把末位的 9 去掉，直到沒有 9 爲止。

用 k = 192, n = 192 來當範例。
10k = 1920 > n ，因此不能選擇 1920。
k/10 = 19，末位爲 9，因此需要再減少位數。
k/10 = 1，末位不爲 9，此時符合條件，因此下一個數字爲 2。

接下來就是不斷找字典序的下一個數字，直到找到 n 個數字爲止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
vector<int> lexicalOrder(int n) {
    vector<int> ans = {1};
    int i = 1;
    while (ans.size() < n){
        if (i * 10 <= n){
            i *= 10;
        }
        else {
            while (i + 1 > n || i % 10 == 9){
                i /= 10;
            }
            i++;
        }
        ans.push_back(i);
    }
    return ans;
}

time complexity: $O(n)$
space complextiy: $O(1)$