题目描述

我们定义 顺次数 为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。

样例

输出：low = 100, high = 300
输出：[123,234]

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

限制

• 10 <= low <= high <= 10^9

算法

(递归枚举) $O(L \log L)$

1. 采取递归枚举的方式，每次在当前数字后边添加数字，然后判断是否符合答案。
2. 最后需要将答案排序。

时间复杂度

• 由于合法的数字的个数在 $O(L)$ 的范围，$L$ 为数位的长度，但最后需要排序，故时间复杂度为 $O(L \log L)$。

空间复杂度

• 递归需要额外 $O(L)$ 的系统栈空间。

C++ 代码

class Solution {
public:
    void solve(int num, int low, int high, vector<int>& ans) {
        if (num > high)
            return;

        if (low <= num)
            ans.push_back(num);

        if (num % 10 < 9)
            solve(num * 10 + num % 10 + 1, low, high, ans);
    }

    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;

        for (int i = 1; i <= 9; i++)
            solve(i, low, high, ans);

        sort(ans.begin(), ans.end());

        return ans;
    }
};