【LeetCode每日一题】386. 字典序排数【中等】

给你一个整数 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

题解： 这道题比较好想，第一个元素肯定是1，如果末尾加0之后还在n的范围内，那么就可以进行更新，如果末尾为9或者当前值已经为n，那么就需要去掉末尾上的数字。

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans(n);
        int num = 1;
        for(int i = 0; i < n; i++){
            ans[i] = num;
            if(num * 10 <= n){
                num *= 10;
            }
            else{
                while(num % 10 == 9 || num + 1 > n){
                    num /= 10;
                }
                num++;
            }
        }
        return ans;
    }
};