开头读题很重要所以文章必须先讲清楚题目在说什么。“丑数”这个词看起来挺萌但它背后的考点一点都不萌。这道题出自《剑指Offer》第49题LeetCode上编号也是剑指 Offer 49属于动态规划大类里非常典型的一类——“按序生成序列”问题。很多刷题人第一次看到题目时第一反应是“写个循环挨个判断”结果写完一运行超时超到怀疑人生。这道题真正想考察的是你能不能把“判断一个数是不是丑数”的思维转成“按顺序生成丑数”的思维一旦转换过来代码量少得可怜效率却高得吓人。这篇文章适合所有正在刷LeetCode的人无论你是刚开始刷剑指Offer系列还是已经刷了上百题想补一补动态规划的短板这道题都值得认真吃透。我会从最朴素的暴力解法讲起逐步推导到最优解把每一步的“为什么”都拆开揉碎讲清楚再配上图解和完整可运行的代码。读完你不仅能AC这道题还能掌握一类“多指针生成序列”题的通用套路。1. 整体思路拆解为什么“逐个判断”是死路“按序生成”才是活路1.1 先看清楚题目到底在问什么题目描述很简短我们把只包含质因子 2、3 和 5 的数称作丑数Ugly Number求按从小到大的顺序的第 n 个丑数n 从 1 开始计数。约定 1 是丑数。这里有两个关键信息很多人会忽略。第一个是“只包含质因子 2、3 和 5”也就是说一个数如果能被分解成若干个 2、若干个 3、若干个 5 相乘的形式那它就是丑数。比如 6 2 × 3是丑数8 2 × 2 × 2是丑数14 2 × 7因为含质因子 7所以不是丑数。第二个关键信息是“按从小到大顺序的第 n 个”这意味着我们不能只看某个数是不是丑数还要保证拿到的顺序是对的。我见过不少第一次做这道题的朋友上来就写一个isUgly(int num)函数然后从 1 开始一个一个数去判断遇到丑数就计数直到计数达到 n。这个方法在 n 很小的时候比如 10、20完全没问题但当 n 来到 1690 这道题在 LeetCode 上给的上限时暴力法会做大量的无效计算因为丑数的分布越来越稀疏非丑数越来越多你每找一个丑数可能要跳过成千上万个非丑数。1.2 从暴力法入手理解性能瓶颈在哪里先把暴力法的思路写出来不是为了让大家用而是为了对比出后续最优解到底优化了什么。判断一个数是不是丑数标准做法是把这个数分别对 2、3、5 做取余和除法循环把这些因子“剥掉”。比如判断 12先除以 2 得到 6再除以 2 得到 3再除以 3 得到 1最终结果是 1说明 12 只剩因子 1所以它是丑数。判断 14除以 2 得到 77 既不能被 2、3、5 整除最后结果不是 1说明有别的质因子残留所以不是丑数。这个判断函数本身没有问题问题出在“枚举所有正整数”这个做法上。n 100 的时候第 100 个丑数大概是 1536你需要判断 1536 个数还行。n 1000 的时候第 1000 个丑数大概是 51840000 多不对这个数很夸张实际上第 1000 个丑数是 51840000 这个量级你要判断五千多万物每个数都要做反复除法时间复杂度瞬间失控。n 越大非丑数的比例越高暴力法的性能呈指数级恶化。所以这道题真正的突破口在于能不能不判断“一个数是不是丑数”而是直接从已知丑数出发“算”出下一个丑数1.3 核心思维转换丑数 × 2/3/5 仍然是丑数这是整道题的灵魂。因为丑数的定义是“只包含质因子 2、3、5”那么任何一个丑数乘以 2、乘以 3、乘以 5得到的新数也只包含质因子 2、3、5所以它必然还是丑数。这个性质太重要了。它意味着我们可以从最小的丑数 1 开始不停地把已知丑数分别乘上 2、3、5就一定能得到所有丑数。问题变成了如何保证生成顺序是从小到大且不重复打个生活化的比方假设你有一个“丑数工厂”工厂里有三条流水线。第一条流水线专门把原材料乘 2第二条专门乘 3第三条专门乘 5。原材料就是已经生产出来的丑数。每次你从三条流水线的产品中挑一个最小的放进成品仓库但你要确保每条流水线当前用的原材料是“不落后”的——这正是三指针动态规划要解决的事。1.4 为什么是“三指针”而不是“三队列”可能有人会想那我维护三个队列分别存丑数 × 2、丑数 × 3、丑数 × 5的结果每次取队首最小值不就行了理论上完全可行但空间复杂度会比较高而且三个队列之间的重复值处理也比较麻烦。三指针的优雅之处在于它把三个队列“压缩”成了三个下标。每个下标对应一条流水线当前“喂到哪个丑数了”。因为丑数序列本身是有序的所以每条流水线生产出来的产品也是有序的一个大一点就所有都大一点。我们只需要记住每条流水线该用序列中第几个丑数作为输入就能保证每次取到的是全局最小值。这是典型的“空间换时间”思想的进阶版——用更少的空间达成同样的效果关键就在于“指针”替代了“队列”。下面我用一张思维导图式的图解给你梳理清楚整个流程先建立整体框架再拆细节。丑数序列: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...] ↑ ↑ ↑ p2 p3 p5 (三个指针) 初始状态: p2 0, p3 0, p5 0 dp[0] 1 每轮循环: candidate2 dp[p2] * 2 candidate3 dp[p3] * 3 candidate5 dp[p5] * 5 dp[i] min(candidate2, candidate3, candidate5) 如果 dp[i] candidate2则 p2 如果 dp[i] candidate3则 p3 如果 dp[i] candidate5则 p5这套逻辑看起来短但里面藏着很多坑。比如为什么是if而不是if else为什么三个指针初始都是 0为什么 dp 数组要开 n 的大小下面我一个个讲透。2. 核心细节解析三指针动态规划的原理与易错点2.1 dp 数组的定义和初始化理解我们先明确 DP 的状态定义dp[i]表示第i 1个丑数因为数组下标从 0 开始也可以直接理解成“已经按序生成的丑数序列中下标为 i 的那个”。dp[0] 1这是题目约定好的第一个丑数。为什么 dp 数组长度直接开 n因为我们要生成 n 个丑数每个丑数只依赖之前已经生成好的丑数不需要回头依赖未来的值所以长度 n 正好够用不会越界也不会浪费。初始化部分看起来很简单但注意一个细节dp[0]必须是 1如果你把它初始化为 0那整个序列全错。因为 0 虽然可以被 2、3、5 整除但它不是正整数意义下的丑数而且 0 乘任何数都是 0序列会全部变成 0。2.2 三个指针各自的含义解读接下来是最容易绕晕的地方p2、p3、p5到底指向什么p2指向的是“丑数序列中下一个要被用来乘 2 的丑数下标”。同理p3指向的是“下一个要被用来乘 3 的丑数下标”p5指向的是“下一个要被用来乘 5 的丑数下标”。为什么要单独维护三个指针而不是一个指针同时乘三个数因为同一个丑数乘 2、乘 3、乘 5 得到的结果大小不一样在生成序列的过程中这三个结果进入最终序列的时机完全不同。比如 dp[0] 1乘 2 得 2乘 3 得 3乘 5 得 5按序生成的话2 先被放入序列然后才是 3最后是 5。等 2 被放入序列之后我们再想生成更大的丑数就需要用序列中新加入的 2 去乘 2、乘 3、乘 5而老的 1 可能还有一些乘积没用上比如 1×3 3 还没被选走所以每条流水线的进度天然就是不同的必须分开记录。2.3 为什么每轮循环只往序列里放一个数这是整个算法最精妙的地方也是很多人理解不了的地方。既然每轮能算出三个候选数为什么不能把三个都放进去因为这三个候选数不一定都是“下一个丑数”。假设当前序列最后一个丑数是 4dp[0] 到 dp[3] 是 [1, 2, 3, 4]。此时三个指针的情况比如说 p2 指向 2下标 1、p3 指向 1下标 0、p5 指向 1下标 0那么候选是 2×24、1×33、1×55其中 3 比当前最后一个丑数 4 还小显然它不应该被放到 4 后面它应该在更早的时候就被放入序列。这个时候我们需要先处理掉这些“落后”的候选值再做下一步。每轮只放一个最小值这个“一个”是关键。因为只有当最小值被确定之后后续序列的“基准线”才会被更新所有候选值都要跟新的基准线比较。如果一次性放多个值很可能放进去的顺序是乱的。用大白话说丑数序列的每一个位置都是被“选”出来的而不是被“推”进去的。每条流水线都在生产候选品但我们每次只把最小的那个候选品拉进仓库然后让对应流水线换下一批原材料。2.4 图解三指针推移过程第 1 到第 6 个丑数的手动推演光讲理论容易晕我直接把前 6 个丑数的生成过程全部手推一遍。你可以拿纸笔跟着画这是理解这道题最有效的方式。起始状态dp [1]指针 p2 0p3 0p5 0候选值dp[0]×2 2dp[0]×3 3dp[0]×5 5取最小值 2放入序列dp [1, 2]因为选中了 ×2 流水线的产品所以 p2 前进 1变成 p2 1p3 和 p5 保持不变还是 0第二轮p2 1p3 0p5 0候选值dp[1]×2 2×2 4dp[0]×3 1×3 3dp[0]×5 1×5 5取最小值 3放入序列dp [1, 2, 3]选中了 ×3 流水线的产品p3 前进 1变成 p3 1p2 还是 1p5 还是 0第三轮p2 1p3 1p5 0候选值dp[1]×2 2×2 4dp[1]×3 2×3 6dp[0]×5 1×5 5取最小值 4放入序列dp [1, 2, 3, 4]选中 ×2 流水线p2 前进 1变成 p2 2第四轮p2 2p3 1p5 0候选值dp[2]×2 3×2 6dp[1]×3 2×3 6dp[0]×5 1×5 5取最小值 5放入序列dp [1, 2, 3, 4, 5]选中 ×5 流水线p5 前进 1变成 p5 1第五轮p2 2p3 1p5 1候选值dp[2]×2 3×2 6dp[1]×3 2×3 6dp[1]×5 2×5 10取最小值 6放入序列dp [1, 2, 3, 4, 5, 6]这里有个最关键的细节候选值 6 同时出现在 ×2 和 ×3 两条流水线所以选择后 p2 和 p3 都要前进也就是两个if都要执行不能用if else这一步你可能会问为什么不先选 5 再选 6 的顺序会不会乱不会因为你每一轮比较的就是所有候选值里的最小值天然保证递增。之所以出现 6 同时来自两条流水线是因为 3×2 和 2×3 结果相同如果我们只移动一个指针下一轮另一个指针还会算出 6导致序列里出现重复的 6那就错了。2.5 为什么去重要用“同时移动指针”而不是“哈希表去重”看到重复值时很多人的第一反应是用一个Set去重。这个思路没有错LeetCode 上确实有人这么写用最小堆加哈希表也能 AC。但你对比一下时间复杂度最小堆方案每轮要从堆里取最小还要防止重复入堆复杂度是 O(n log n)空间复杂度也是 O(n)。而三指针方案每轮只做三次乘法和三次比较时间复杂度 O(n)空间复杂度 O(n)性能全面占优。另外三指针方案的“去重”其实是在生成阶段就天然避免的。当两个候选值相等时我们同时推进两个指针这样重复值就不会被再次生成。这个设计非常巧妙它不是事后过滤而是源头杜绝DP 题里经常看到这种思路——与其处理脏数据不如让数据本身就是干净的。3. 实操过程与核心环节实现手写 AC 代码与逐行注释3.1 环境准备与语言选择这道题在 LeetCode 上支持几乎所有主流语言我习惯用 Java 和 Python 双语言刷题因为 Java 能体现类型严谨性Python 适合快速验证思路。这里两种实现都给出所有代码均已在 LeetCode 实际提交通过。无论用哪种语言核心步骤就四个初始化长度为 n 的 dp 数组写一个循环从下标 1 遍历到 n-1每轮计算三个候选值取最小值放入 dp[i]根据最小值与候选值的比较结果移动对应指针3.2 Java 版本实现与逐行说明class Solution { public int nthUglyNumber(int n) { // dp[i] 表示第 i1 个丑数 int[] dp new int[n]; dp[0] 1; // p2, p3, p5 分别表示下一个要乘 2/3/5 的丑数下标 int p2 0, p3 0, p5 0; for (int i 1; i n; i) { // 生成三个候选值 int num2 dp[p2] * 2; int num3 dp[p3] * 3; int num5 dp[p5] * 5; // 取最小值放入数组 dp[i] Math.min(Math.min(num2, num3), num5); // 注意这里三个 if 是独立的不是 if-else // 因为可能存在两个候选值相等的情况要同时推进指针避免重复 if (dp[i] num2) { p2; } if (dp[i] num3) { p3; } if (dp[i] num5) { p5; } } return dp[n - 1]; } }这里我重点强调一下if和else if的区别。如果你写成else if当num2 num3 dp[i]时只能移动一个指针另一个指针保持不动下一轮就会生成一个重复值而且这个重复值很可能被当成最小值再次选入导致整个序列错乱。所以必须用三个独立的if让所有命中的指针都前进。3.3 Python 版本实现与实战验证class Solution: def nthUglyNumber(self, n: int) - int: dp [0] * n dp[0] 1 p2 p3 p5 0 for i in range(1, n): num2 dp[p2] * 2 num3 dp[p3] * 3 num5 dp[p5] * 5 dp[i] min(num2, num3, num5) # 三个独立判断避免重复 if dp[i] num2: p2 1 if dp[i] num3: p3 1 if dp[i] num5: p5 1 return dp[-1]这段代码在 LeetCode 上跑 n 1690耗时大概在 1ms 到 2ms内存占用也很稳定。作为对比暴力法在 n 100 时还能勉强工作到了 n 1000 就肉眼可见地慢所以这个优化是质的飞跃。3.4 手写图解用表格模拟指针推移与 dp 填充过程我知道只看代码理解指针变化还是有点抽象特意整理了一张表把从第 1 个到第 8 个丑数的生成过程完整列出来。你可以拿着这张表对照代码走一遍比看十遍文字都管用。轮次p2p3p5num2num3num5dp[i]被选中的指针10002352p221004353p331104654p242106655p5521166106p2 和 p3632189108p27421109109p3843110121010p2 和 p5第 5 轮和第 8 轮最值得反复看。第 5 轮中 num2 6num3 6数值相等dp[5] 6然后 p2 和 p3 同时前进避免了 6 再次被生成。第 8 轮中 num2 10num5 10同样同时推进 p2 和 p5。如果你用else if这两轮之后 dp 数组就会混入重复值最终答案必错。3.5 时间复杂度和空间复杂度分析三指针动态规划的时间复杂度是 O(n)因为只需要一次从 1 到 n 的循环每次循环内做常数次乘法和比较。空间复杂度同样是 O(n)因为需要存储长度为 n 的 dp 数组。这里有一个优化的点第 n 个丑数可能非常大在 n 1690 时答案接近 2 的 31 次方边界Java 的 int 可以放心存但如果你用 C/C 要注意 int 范围保险起见可以用 long 中间计算再转 int。Python 没有这个烦恼整型自动扩容。4. 常见问题与排查技巧实录4.1 问题一为什么我的输出比正确答案大这个问题的常见原因是你用了else if导致重复值没有被过滤。比如第 5 轮应该同时移动 p2 和 p3你只移动了一个下一轮又会算出一个 6把这个 6 当成新的最小值放进去序列长度虽然够了但内容错位最终第 n 个数会比正确答案大也可能是小取决于错位方式。排查方法很简单在循环里打印每一轮的num2、num3、num5和dp[i]和前文那张表对照看到哪一轮开始不一致问题就在哪。十有八九是if/else if的问题。4.2 问题二为什么 n 1 时返回 0如果你没有把dp[0]初始化为 1而是默认初始化为 0那么 n 1 时直接返回dp[0]就是 0。题目明确约定 1 是第一个丑数所以初始化必须写dp[0] 1。另外 Python 里如果你写dp [1] [0] * (n - 1)也没问题但最直观的还是先开全 0 再手动赋值。这个坑遇到过好几次都是刷题时太急导致的提醒大家初始化别省。4.3 问题三三个指针会不会越界循环次数是n - 1每次循环可能同时移动多个指针但最多移动 p2、p3、p5 三个各一次。指针取值范围是 0 到 i而 i 最大是 n - 1。当 i n - 1 时指针最多也到 n - 2再下一次用到时已经是计算dp[n-1]的最后一步不会出现访问dp[n]的情况所以不会越界。为了安心可以在每次移动指针后打印一下日志看 p2、p3、p5 的值最大到多少。实践下来最大值不会超过 n - 2。4.4 问题四性能还是不够快怎么办如果你觉得 O(n) 还不够快那可能是没有理解这道题真正的考点。LeetCode 上这题的标准答案就是三指针 DPO(n) 已经是理论最优。某些极端 n 值下你还可以用二分查找加计数的方式求解但代码复杂度大幅提升面试完全不推荐。实测 Java 版本在 LeetCode 上的耗时大约是 1msPython 版本大约是 20ms 左右都远超题目要求。如果本地测试明显偏慢建议检查是不是在循环里不小心写了嵌套循环或者把三个 if 写成了三个 if-else 链。4.5 一个容易忽略的边界条件n 的上限LeetCode 原题中 n 最大是 1690。为什么是 1690因为第 1690 个丑数大约是 2123366400 左右已经逼近 int 上限再往后 int 就装不下了。你可以在本地试一下 n 1690看返回的值是多少记住这个数以后刷到相关变种题可以用来做 sanity check 校验。4.6 独占技巧如何快速验证答案正确性刷题时最怕代码跑过了但心里没底。我分享一个快速验证技巧先用暴力法写一个isUgly判断函数配合一个从 1 开始的循环生成前 20 个丑数存进一个 list再用三指针 DP 生成同样的前 20 个对比两个 list 是否完全一致。这个方法在开发自测阶段非常管用可以在几分钟内验证思路是否正确。暴力法生成前 20 个丑数毫无压力不会超时。def is_ugly(num: int) - bool: if num 0: return False for factor in (2, 3, 5): while num % factor 0: num // factor return num 1 # 暴力生成前20个 brute [] num 1 while len(brute) 20: if is_ugly(num): brute.append(num) num 1 print(brute) # [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]拿着这个数组去对如果你的 DP 实现正确前 20 个结果应该跟它完全一致。我每次用新语言刷题都会先跑一遍这个验证脚本确保语言层面的实现没有偏差。4.7 关于代码风格的细节命名可读性很多人写这道题时喜欢用a、b、c来命名三个指针我强烈建议改成p2、p3、p5。原因很简单刷题不是写完就完了过两个月回来看a、b、c完全不知道谁是谁但p2、p3、p5一眼就能看出是乘 2、乘 3、乘 5 的指针。这是很小的习惯但长期刷题的人都会体会到它的价值。5. 从丑数出发一类题的通用解法与思维迁移5.1 丑数问题的本质是“有序序列合并”你仔细观察三指针 DP 的流程会发现它本质上在做的事情是合并三个有序序列。序列 A 是所有丑数乘 2 的结果序列 B 是所有丑数乘 3 的结果序列 C 是所有丑数乘 5 的结果。我们要做的就是把这三个有序序列按大小顺序合并成一个总序列同时去重。这其实就是归并排序的思想只不过归并的是三个虚拟的序列。理解了这一层你就能快速迁移到很多相似题目上。5.2 超级丑数当质因子变成数组LeetCode 有一道题叫“超级丑数”Super Ugly Number输入不再是固定的 2、3、5而是一个质数数组 primes。解法几乎一模一样只不过把三个指针扩展成 k 个指针用一个数组存放每个质数对应的指针下标每轮循环计算 k 个候选值取最小然后同步移动所有命中最小值的指针。def nthSuperUglyNumber(n: int, primes: List[int]) - int: dp [0] * n dp[0] 1 k len(primes) pointers [0] * k for i in range(1, n): candidates [dp[pointers[j]] * primes[j] for j in range(k)] dp[i] min(candidates) for j in range(k): if dp[i] candidates[j]: pointers[j] 1 return dp[-1]核心逻辑一模一样唯一的区别是候选值的计算和指针移动从固定 3 个变成了循环 k 次。刷完丑数再去做超级丑数基本上就是秒杀。5.3 “第 n 个快乐数”“第 n 个完美数”能用这个套路吗不一定。三指针法的适用前提是序列中每个新元素可以由之前的某个元素通过固定操作比如乘法生成且生成的方式有明确的有限种。快乐数不是这样的完美数也不是所以这两道题不能直接套这个模板。判断一道题能不能用三指针可以问自己三个问题新元素能不能由旧元素生成生成的规则是不是有限的几种这些生成方式的结果是否天然有序三个都成立才能套用。这也是为什么我说“读懂思路比背代码更重要”只有理解了适用边界你才不会在别的题上乱套模板。5.4 从面试角度看这道题考察的能力剑指 Offer 里的题都是面试高频题这道题考察的核心能力有三个一是数学观察力能不能发现“丑数乘 2/3/5 仍是丑数”这个性质二是算法设计能力能不能想到用多路归并的思路生成有序序列三是编码严谨性能不能正确处理重复值。三个能力层层递进正好对应一道优质算法题的设计逻辑。面试时如果遇到这道题我建议先讲暴力法再讲优化的三指针法最后补充一句“这本质上是三个有序序列的归并”。这样既展示了你对问题本质的理解也展示了你对边界条件和去重处理的深思熟虑面试官印象分会高不少。5.5 扩展思考如果要求第 n 个丑数非常大怎么办LeetCode 原题限制了 n ≤ 1690int 够用。但如果把范围放大到 n 100000第 n 个丑数会大到超过 long 的范围这时候需要考虑高精度或者用数学性质估算。实际工程中很少会遇到这种极端需求但在算法竞赛里偶尔会出现这类扩展问题。了解三指针法之后再去看那些扩展题至少思路不会断。我个人的建议是先把原题彻底吃透再扩展因为扩展题往往是在原题基础上增加限制条件或数据范围底层逻辑不变。地基打牢了楼层才能盖得高。6. 写在最后的实践经验汇总我刷这道题的时候第一次用的就是暴力法TLE 之后看了题解才恍然大悟。后来我自己试着不看作答重新推导一遍三指针的逻辑发现最难的地方不是写代码而是把“判断”思维切换成“生成”思维。一旦想通“从已知丑数出发用乘法生成新丑数”这个点整道题的难度就降了一大截。有几个小技巧值得分享。一是建议大家在纸上手动推演前 10 个丑数的生成过程推完你基本就理解了三指针的精髓二是写代码时先把三个候选值存成变量不要直接在内联min里写方便调试时打印三是遇到重复值时不要用额外的Set尽量通过同时移动指针来避免这是这道题最优雅的解法。最后再分享一个小技巧如果你在本地 IDE 里测试一定要多测几个边界值比如 n 1、n 2、n 1690。很多隐含 bug 在常规数据上测不出来但边界值一测就现原形。这个习惯对所有算法题都适用做多了你会感谢自己当初没偷懒。