I use a finite state machine to know the current state.

Now we have three things to do.

State 0. Add zeros as more as possible

State 1. Increment the number

State 2. When the number has a carry bit, remove all zeros, return to state 0. Or, if the number equals to the input, divide it by ten (I did it in state 0)

```
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> answer;
if(n < 1) return answer;
int num = 1;
int state = 0;
int cnt = n;
while(cnt != 0){
switch(state){
case 0: // Append zero
if(num <= n){
answer.push_back(num);
cnt--;
num *= 10;
}
else{
num /= 10;
state = 1;
}
break;
case 1: // Increasing
if(num % 10 != 9 && num < n ){
num++;
answer.push_back(num);
cnt--;
}
else{
num++;
state = 2;
}
break;
case 2: // If carry bit is necessary, remove all zeros.
while(num % 10 == 0){
num /= 10;
}
state = 0;
}
}
return answer;
}
};
```