标签: 枚举
难度: 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运行时间: 24 ms
内存: 16.1 MB
from typing import List
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
result = [] # 存储结果的列表
for length in range(1, 10): # 顺次数的长度从1到9
for start in range(1, 10 - length + 1): # 确定起始数字，最大为9减去长度加1
num = 0 # 用于构建顺次数的变量，初始化为0
# 构建顺次数的过程，同时检查是否在范围内
valid = True # 标记当前构建的顺次数是否有效（在范围内）
for i in range(length): # 遍历每一位数字
digit = start + i # 计算当前位的数字
num = num * 10 + digit # 将当前数字加到顺次数的最低位
if num > high: # 如果当前数字已经大于high，提前终止内层循环并标记为无效
valid = False
break
if num >= low and valid: # 如果当前数字在范围内且之前也都在范围内，则添加到结果列表中
if i == length - 1: # 只有在构建完整个顺次数后才添加到结果列表中，避免重复添加
result.append(num)
return result # 返回结果列表
这个题解的基本思路是穷举所有可能的顺次数，并检查它们是否落在给定的区间 [low, high] 内。顺次数是由连续递增的数字组成，如 123 或 456。题解首先考虑顺次数可能的长度，从1到9，然后为每个长度生成所有可能的顺次数。这是通过固定顺次数的起始数字，然后逐位构建整数完成的。生成的顺次数如果大于 high，就中断当前长度的进一步探索，避免无效的计算。若顺次数同时大于或等于 low 且小于或等于 high，则将其添加到结果列表中。
时间复杂度: O(1)，因为生成顺次数的总数是有限的。
空间复杂度: O(1)，因为输出列表的大小由有限的顺次数决定。
from typing import List
class Solution:
def sequentialDigits(self, low: int, high: int) -> List[int]:
result = [] # 存储结果的列表
for length in range(1, 10): # 顺次数的长度从1到9
for start in range(1, 10 - length + 1): # 确定起始数字，最大为9减去长度加1
num = 0 # 用于构建顺次数的变量，初始化为0
valid = True # 标记当前构建的顺次数是否有效（在范围内）
for i in range(length): # 遍历每一位数字
digit = start + i # 计算当前位的数字
num = num * 10 + digit # 将当前数字加到顺次数的最低位
if num > high: # 如果当前数字已经大于high，提前终止内层循环并标记为无效
valid = False
break
if num >= low and valid and i == length - 1: # 如果当前数字在范围内且之前也都在范围内，且构建完整个顺次数后才添加到结果列表中，避免重复添加
result.append(num)
return result # 返回结果列表
顺次数是由连续递增的数字组成，因此最长的顺次数是由1到9这9个连续数字构成的。由于数字只有1至9，任何长度超过9的序列都无法满足连续递增的特性，因为这将需要第10个不同的连续数字，而这在1到9的范围内是不存在的。因此，顺次数的最大长度为9，不需要考虑更长的序列。
在算法设计中，通过控制起始数字的选择（`start`），确保生成的每一位数字都不会超过9。起始数字最大可取`9 - length + 1`，这保证了即使在长度最大的情况下，加上起始数字之后的结果也不会超过9。例如，如果长度为3，起始数字最大为7（即7 + 2 = 9），从而避免了任何一位数字超过9的情况。
顺次数是由连续增加的数字组成，如果在构建过程中某个顺次数已经超过了high值，则随着数字的进一步增加，它只会变得更大，不可能重新变小回到low到high的区间内。因此，一旦顺次数超过high值，便可以立即判定当前顺次数为无效，并终止进一步的数字添加，以节省不必要的计算资源。
在顺次数的构建过程中，只有当整个数字完全构建完成后，才能确定这个数是否落在指定的区间[low, high]内。虽然在构建过程中可以提前终止超过high的无效顺次数，但对于是否低于low的判断只能在顺次数完全形成后进行。此外，顺次数的每一位是连续增加的，我们需要整个顺次数构建完成后才能准确判断其是否符合要求。