LeetCode 每日一题笔记

0. 前言

• 日期：2026.07.01
• 题目：1291. 顺次数
• 难度：中等
• 标签：字符串、枚举、滑动窗口

1. 题目理解

问题描述 顺次数定义：每一位数字都比前一位数字大1的整数。给定区间 [low, high]，返回区间内全部顺次数，结果按升序排列。

示例

输入：low = 100, high = 300 输出：[123,234] 解释：123、234 是区间内仅有的顺次数。

2. 解题思路

核心观察

1. 所有顺次数都来自字符串 "123456789" 的连续子串；
2. 顺次数位数范围由 low、high 的数字长度决定；
3. 优化方向：纯数字生成替代字符串截取，消除字符串转换与解析的if判断开销。

算法步骤

字符串原版：

1. 基础串 123456789，计算区间数字最小、最大位数；
2. 按位数逐层枚举，滑动截取对应长度子串转为数字；
3. 判断数字落在区间则加入结果。

数字生成优化版：

1. 枚举起始数字1~8，循环追加下一位生成顺次数；
2. 数字超出high则终止当前分支；数字≥low时直接存入结果；
3. 天然升序，无需额外排序，减少区间判断分支。

3. 代码实现

package lc1291;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> res = new ArrayList<>();
        // 固定基础串：所有顺次数都是该串连续截取
        String base = "123456789";
        // low的数字位数
        int lenMin = String.valueOf(low).length();
        // high的数字位数
        int lenMax = String.valueOf(high).length();

        // 遍历每一种数字长度
        for (int len = lenMin; len <= lenMax; len++) {
            // 滑动窗口：截取长度为len的连续子串，窗口起点最大到 9-len
            for (int start = 0; start <= 9 - len; start++) {
                // 截取 [start, start+len) 连续字符，就是顺次数字符串
                String numStr = base.substring(start, start + len);
                int num = Integer.parseInt(numStr);
                // 判断是否落在区间内
                if (num >= low && num <= high) {
                    res.add(num);
                }
            }
        }
        return res;
    }
}

4. 代码优化说明

import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
    List<Integer> ans = new ArrayList<>();
    // 枚举所有起始数字1~8，逐位生成顺次数
    for(int start = 1; start <= 8; start++){
        int cur = start;
        int next = start + 1;
        // 持续追加下一位数字
        while(cur <= high && next <= 9){
            cur = cur * 10 + next;
            next++;
            // 满足区间直接加入，合并区间判断逻辑
            if(cur >= low){
                ans.add(cur);
            }
        }
    }
    return ans;
}
}

5. 复杂度分析

• 字符串原版 时间复杂度：$O(1)$，顺次数总数固定有限；存在字符串截取、类型转换、区间多层if判断 空间复杂度：$O(1)$，基础串固定长度，结果集容量上限固定
• 数字生成优化版 时间复杂度：$O(1)$，纯数值运算，消除字符串相关操作，仅保留一层区间判断if 空间复杂度：$O(1)$，无字符串缓存，仅常数数值临时变量

6. 总结

• 核心：顺次数由连续递增数字构成，可枚举生成全部合法数字；
• 优化亮点：纯数字运算替代字符串截取与解析，减少字符串转换分支；生成天然升序，无需按长度分层循环；
• 关键点：顺次数上限仅到123456789，总枚举数量恒定，复杂度为常数级。