Medium

题目描述

如果一个整数的每一位数字都比前一位数字大1，那么这个整数就是顺次数。

返回在 [low, high] 范围内所有的顺次数，结果需要按升序排列。

示例 1：

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

示例 2：

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

提示：

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

解题思路

这道题要求找出给定范围内的所有顺次数。顺次数的特点是每一位数字都比前一位大1，比如123、234、1234等。

解法分析：

  1. 枚举法（推荐）： 由于顺次数的特殊性质，我们可以直接生成所有可能的顺次数。对于每个起始数字1-9，我们可以依次添加下一个连续数字来构造顺次数。比如从1开始可以得到12、123、1234等，从2开始可以得到23、234、2345等。

  2. BFS/DFS生成： 也可以使用队列或递归的方式，从每个起始数字开始，不断添加下一个连续数字，直到超出范围。

具体实现思路：

  • 对于每个起始数字i（1≤i≤9），构造以i开头的所有顺次数
  • 从当前数字开始，不断乘以10并加上下一个连续数字
  • 当下一个数字超过9或生成的数字超过high时停止
  • 将所有在[low, high]范围内的顺次数收集起来并排序

由于顺次数的数量很有限（最多只有36个），直接枚举生成是最简单有效的方法。

代码实现

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> result;
        
        for (int i = 1; i <= 9; i++) {
            int num = i;
            int nextDigit = i + 1;
            
            while (nextDigit <= 9) {
                num = num * 10 + nextDigit;
                if (num >= low && num <= high) {
                    result.push_back(num);
                }
                if (num > high) break;
                nextDigit++;
            }
        }
        
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        result = []
        
        for i in range(1, 10):
            num = i
            next_digit = i + 1
            
            while next_digit <= 9:
                num = num * 10 + next_digit
                if low <= num <= high:
                    result.append(num)
                if num > high:
                    break
                next_digit += 1
        
        return sorted(result)

public class Solution {
    public IList<int> SequentialDigits(int low, int high) {
        var result = new List<int>();
        
        for (int i = 1; i <= 9; i++) {
            int num = i;
            int nextDigit = i + 1;
            
            while (nextDigit <= 9) {
                num = num * 10 + nextDigit;
                if (num >= low && num <= high) {
                    result.Add(num);
                }
                if (num > high) break;
                nextDigit++;
            }
        }
        
        result.Sort();
        return result;
    }
}

var sequentialDigits = function(low, high) {
    const result = [];
    
    for (let i = 1; i <= 9; i++) {
        let num = i;
        let nextDigit = i + 1;
        
        while (nextDigit <= 9) {
            num = num * 10 + nextDigit;
            if (num >= low && num <= high) {
                result.push(num);
            }
            if (num > high) break;
            nextDigit++;
        }
    }
    
    return result.sort((a, b) => a - b);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(1) - 最多生成36个顺次数，常数时间
空间复杂度O(1) - 除了返回结果，只使用常数额外空间