subject

   Give you an integer n , Returns the range in dictionary order [1, n] All integers in .
   You have to design a time complexity of O(n) And the use of O(1) Extra space algorithm .

Example 1：
Input ：n = 13
Output ：[1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2：
Input ：n = 2
Output ：[1,2]

Tips ：

• 1 <= n <= 5 * 104

answer

Using constant space dfs
link

Explain

class Solution {
    
public:
    vector<int> lexicalOrder(int n) {
     // Using stack dfs, Can pass , But it is uncertain whether it meets the space-time complexity of the subject requirements 
        vector<int> ans;
        stack<int> buf;
        int curnum = 1;
        buf.push(curnum);
        while (!buf.empty()) {
    
            curnum = buf.top();
            buf.pop();
            while (curnum <= n) {
    
                ans.push_back(curnum);
                if (curnum % 10 < 9) {
    
                    buf.push(curnum+1);
                }
                
                curnum *= 10;
            }
        }
        return ans;
    }
};