---

1291. 顺次数

• 标签：枚举
• 难度：中等

题目链接

• 1291. 顺次数 - 力扣

题目大意

描述：给定两个整数 $low$ 和 $high$。

要求：返回 $[low, high]$ 范围内所有顺次数（各位数字依次递增的整数，如 $123$、$234$、$34567$ 等）的列表，按升序排列。

说明：

• $10 \le low \le high \le 10^{9}$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：枚举

1. 核心思想

顺次数的特点是"每位递增 $1$"，且位数从 $2$ 到 $9$（因为 $10$ 位及以上的顺次数不存在，只有 $0$-$9$ 十个数字）。

顺次数的总数非常有限：

• 位数 $2$：$12, 23, 34, 45, 56, 67, 78, 89$（共 $8$ 个）
• 位数 $3$：$123, 234, \dots, 789$（共 $7$ 个）
• ...
• 位数 $9$：$123456789$（共 $1$ 个）

总数：$8+7+6+5+4+3+2+1 = 36$ 个。

所以可以直接枚举所有顺次数，检查是否在 $[low, high]$ 范围内。

2. 具体步骤

第 1 步：枚举所有可能的位数 $len$（从 $2$ 到 $9$）。

第 2 步：对每个位数，枚举起始数字 $start$（从 $1$ 到 $10-len$）：

• 依次生成数字 $num = start, start+1, \dots, start+len-1$ 拼接起来的整数。
• 如果 $low \le num \le high$，加入结果列表。

第 3 步：返回结果列表。

3. 结合示例走一遍

$low = 100, high = 300$

• 位数 $2$：$12 \sim 89$ → 都不在 $[100,300]$ 内。
• 位数 $3$：
  • $123$：$100 \le 123 \le 300$ ✓
  • $234$：$100 \le 234 \le 300$ ✓
  • $345$：$345 > 300$ ✗ → 之后的更大，不用再检查。

结果 $[123, 234]$。

思路 1：代码

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        # 枚举位数
        for length in range(2, 10):
            # 枚举起始数字
            for start in range(1, 10 - length + 1):
                num = 0
                # 生成顺次数
                for d in range(length):
                    num = num * 10 + (start + d)
                if low <= num <= high:
                    ans.append(num)
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(1)$，最多生成 $36$ 个数，生成每个数最多 $9$ 位。
• 空间复杂度：$O(1)$，不考虑结果列表。

思路 2：队列 BFS

也可以用 BFS 的方式。从数字 $1$ 到 $9$ 开始入队，每次将最后一位加 $1$ 后拼接在后面，生成新的顺次数。如果新数字在范围内则记录。这种方法的好处是不需要手动枚举位数和起始数字。