<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>

#pragma GCC optimize("Ofast")
#pragma GCC target("tune=native")

class Solution {
public:
    std::vector<int> lexicalOrder(int n) {
        std::vector<int> result;
        result.reserve(n);

        std::vector<int> stack;
        stack.push_back(1);

        int counter = 0;
        while (counter < n) {
            if (stack.back() <= n) {
                ++counter;
                result.push_back(stack.back());

                if (stack.back() * 10 <= n) {
                    stack.push_back(stack.back() * 10);
                } else {
                    ++stack.back();

                    while (!stack.empty() && stack.back() % 10 == 0) {
                        stack.pop_back();

                        if (stack.empty()) {
                            break;
                        }
                        ++stack.back();
                    }
                }
            } else {
                stack.pop_back();
                ++stack.back();
                while (!stack.empty() && stack.back() % 10 == 0) {
                    stack.pop_back();
                    ++stack.back();
                }
            }

        }

        return result;
    }
};

/*

2
10
13
20
24
80
100
110
200
1100

9
10
11
19
20
21
29
30

31
39
40
41
49
50
51
59
60

61
65
69
70
71
78
79
80

90
99
100
101
102
109
110
111

190
191
199
200
201
202
209
210

295
300
305
350
399
400
401
499

500
502
673
890
990
999
1000
1010


1100
29999
39876
40000
40099
40999
41000
49000

*/
11631