Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Example 1:
Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Explanation: The numbers from 1 to 13 sorted lexicographically (as strings) are [1,10,11,12,13,2,3,4,5,6,7,8,9].
Example 2:
Input: n = 2
Output: [1,2]
Explanation: The numbers 1 and 2 are already in lexicographical order.
Example 3:
Input: n = 25
Output: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,3,4,5,6,7,8,9]
Explanation: After 19, the next lexicographical number is 2, then 20-25, then 3, etc.
1 <= n <= 5 * 10^4