# LeetCode 386. Lexicographical Numbers
[LeetCode 386. Lexicographical Numbers](https://leetcode.com/problems/lexicographical-numbers/) (<font color=#FFB800>Medium</font> 67.6%)

<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :

<ul>
<li><code>1 <= n <= 5 * 10^4</code></li>
</ul>

- Solution
這一題的目標是生成從1到n的字典順序排列，藉由控制數字的進位與退位來達成。
- 若當前數字能乘10且不超過n，則將數字乘以10。
- 若乘10會超過n，則直接增加數字，並移除末尾的零，保持字典順序。
- 若數字等於n時，需要退一位再繼續運算。
- 個人覺得這題好難，完全不知道要從哪裡下手。
- 時間複雜度: $O(n)$
- 空間複雜度: $O(n)$

- 程式碼

    class Solution {
    public:
        // This function returns the lexicographical order of numbers from 1 to n
        static vector<int> lexicalOrder(int n) {
            vector<int> ans(n);  // Initialize a vector of size n to store the result
            int x = 1;  // Start from number 1

            // Loop to fill the vector ans with lexicographical order
            for (int i = 0; i < n; i++) {
                ans[i] = x;  // Store the current value of x into the ans vector

                if (x * 10 > n) {  // If expanding x to the next level exceeds n
                    if (x == n) x /= 10;  // Go back one level if x equals n
                    x++;  // Otherwise, increment x

                    // Remove trailing zeros to maintain lexicographical order
                    while (x % 10 == 0) x /= 10;
                }
                else {
                    x *= 10;  // Prefer to expand x to the next level by multiplying by 10
                }
            }
            return ans;
        }
    };

</details>

- reference :
- https://leetcode.com/problems/lexicographical-numbers/solutions/5813848/recursive-dfs-vs-iteration-beats-100