題目
Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

答案

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>();
        int cnt = n - 1;
        int curr = 1;
        list.add(1);
        while(cnt-- >= 1) {
            if(curr * 10 <= n) {
                // Always try to append 0 to the end of number if possible
                curr = curr * 10;
            }
            else if(curr % 10 != 9 && curr + 1 <= n) {
                // If you can't add 0s, add 1!
                curr++;
            }
            else {
                // In this case, try to find a number with smaller lexicographical order
                while((curr / 10) % 10 == 9) {
                    curr = curr / 10;
                }
                curr = curr / 10 + 1;
            }
            list.add(curr);
        }
        return list;
    }
}