Return every integer from 1 through n in lexicographical order: compare their usual decimal representations as strings, from left to right. If one representation is a prefix of another, the shorter one comes first.
Use O(n) time and O(1) extra space, excluding the returned array.
Example 1:
Input: n = 11
Output: [1,10,11,2,3,4,5,6,7,8,9]Explanation: The decimal strings beginning with 1 come first: 1, 10, and 11. They are followed by 2 through 9.
Example 2:
Input: n = 3
Output: [1,2,3]Explanation: The one-digit numbers 1, 2, and 3 are already in lexicographical order.
Example 3:
Input: n = 20
Output: [1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9]Explanation: The sequence starts with 1, then 10 through 19, then 2 and 20, followed by 3 through 9. Numbers are ordered by decimal text rather than numeric size.
Constraints:
1 <= n <= 50000