来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lexicographical-numbers
题目描述
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2
输出：[1,2]
提示：
1 <= n <= 5 * 104
解题思路
由于题目要求时间复杂度为O(n)，所以排序的思路肯定行不通。
使用深度优先遍历的思想，将每一位都枚举出来可以满足时间复杂度的要求，但是如果使用递归方法的深度优先遍历，空间复杂度不满足，所以使用迭代的方式实现深度优先遍历。
代码展示
class Solution { public: vector<int> lexicalOrder(int n) { vector<int> viRet; int iNumber = 1; for(int i = 0; i < n; i++) { viRet.push_back(iNumber); if(iNumber * 10 <= n) { iNumber *= 10; } else { while(iNumber % 10 == 9 || iNumber + 1 > n) iNumber /= 10; iNumber++; } } return viRet; } };
运行结果
