<p>Given an integer <code>n</code>, return all the numbers in the range <code>[1, n]</code> sorted in lexicographical order.</p>

<p>You must write an algorithm that runs in&nbsp;<code>O(n)</code>&nbsp;time and uses <code>O(1)</code> extra space.&nbsp;</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 13
<strong>Output:</strong> [1,10,11,12,13,2,3,4,5,6,7,8,9]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 2
<strong>Output:</strong> [1,2]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

class Solution {
private:
    vector<int> res;

    void top(int& i, int n) {
        if(i == n) {
            res.push_back(i);
        }
        
        i /= 10;
        if(i == 9) {
            i = -1;
            return;
        }
        i++;
    }

    void times(int& i) {
        int src = i;
        while(i/10 and i%10 == 0) {
            i /= 10;
        }

        if(i == 1) {
            i = -1;
            return;
        }

        while(i*10 <= src) {
            res.push_back(i);
            if(i*10 > src) {
                return;
            }
            i *= 10;
            
        }

    }

    int init(int n) {
        int i = 1;
        while(i <= n) {
            res.push_back(i);
            if(i * 10 <= n) {
                i *= 10;
            } else {
                break;
            }
            
        }
        return i;
    }

    void step(int& i, int n) {
        i++;

        if(i%10 == 0) {
            times(i);
            if(i == -1) {
                return;
            }
        }
        if(i >= n) {
            top(i, n);
            if(i == -1) {
                return;
            }
            if(i%10 == 0) {
                times(i);
                if(i == -1) {
                    return;
                }
            }
        }

        res.push_back(i);
    }

public:
    vector<int> lexicalOrder(int n) {

        if(n/10 == 0) {
            for(int i=1; i<=n; i++) {
                res.push_back(i);    
            }
            return res;
        }

        int i = init(n);
        while(true) {
            step(i, n);
            if(i==-1) {
                break;
            }
        }

        return res;
    }
};
13214