1. 先搞清楚这道题到底在问什么1.1 丑数的定义先说清楚什么是“丑”丑数这道题我第一次在刷题平台上看到的时候差点直接跳过名字实在太劝退了。但真正碰过之后我改变看法——这是一道把动态规划核心思想浓缩得很干净的题尤其适合用“先暴力、再优化、最后上 DP”的节奏来理解。定义先背清楚丑数是指只包含质因数 2、3、5 的正整数。质因数就是能整除这个数的质数比如 10 的质因数是 2 和 514 的质因数是 2 和 7。按这个定义6、8、10、12 都是丑数因为它们质因数全在 {2, 3, 5} 里14、21、42 不是因为混入了 7。这里有个经常让人困惑的特例数字 1 被约定为第一个丑数。为什么因为它没有任何质因数空集算作子集数学上约定俗成题目也明确规定了记下来就行后面所有推导都建立在这条约定上。这个定义看起来简单但两道题目从这里开始分岔。第一道题是“给你一个整数判断它是不是丑数”属于一次性的判断问题第二道题是“按从小到大顺序求出第 n 个丑数”属于生成序列的问题。两者难度完全不同动态规划的主角是第二道但第一道是必要的前置理解把判断逻辑吃透了第二道题里的核心思想才顺理成章。1.2 一个系列两问判断与生成先说第一问它真的有手就行。给一个整数 n不断尝试让它被 2、3、5 整除能整除就除除到不能除为止最后看剩下的是不是 1。如果是 1说明它只剩下质因数 2、3、5是丑数如果不是 1说明它含有其它质因子不是丑数。逻辑一句话就能讲清楚代码也是几行。但第二问就有点东西了。如果给你一个 n10让你手工写一下前 10 个丑数你会这么想从 1 开始逐个整数判断1 是2 是3 是4 是5 是6 是7 不是8 是9 是10 是第 10 个是 12按题目序列前 10 个丑数是 1、2、3、4、5、6、8、9、10、12。这个方法对 n10 没问题但题目要的可能 n1690这时问题来了暴力遍历的终止条件是什么你不知道第 1690 个丑数大概落在多大的整数范围内只能一边数一边往后扫。最坏情况很恐怖——丑数出现的密度随数值增大越来越低扫到几亿、几十亿都可能。这里隐藏着一个关键点判断一个数是不是丑数很容易但要在整数范围内按顺序挑出第 n 个丑数暴力法的效率完全不可控。于是你需要换一个思路——不遍历整数而是根据丑数的定义直接“生成”丑数。这就是动态规划的切入点。1.3 为什么这个系列值得认真做我后来带过几个刚入门刷题的同学发现一个普遍现象大家看到“动态规划”四个字就发怵下意识觉得要建复杂的状态转移方程、要画出二维表格。但丑数 II 是一道非常温柔的 DP 入门题它不需要你定义什么 dp[i] 代表“前 i 个物品的最大价值”也不用考虑背包容量只有一个一维数组和三根指针。思维负担小但核心味道已经齐全了你需要在多个候选方案里每次挑一个最小的同时维护好各自推进的起点。这个思想在很多更难的题里都会反复出现值得花一下午把它彻底琢磨透。2. 从暴力到动态规划思路是怎么一步步逼出来的2.1 暴力法看起来很美实际跑不动有的同学一看到第二问第一反应是我写一个 isUgly 函数然后从 1 开始逐个数判断数到第 n 个就返回。代码很简单测试小数据也能跑通过。但你想过没有这个方案连一个明确的循环上界都写不出来只能写成while (count n) num这种形式。因为不知道大丑数长在哪个数值附近只能死等。我们用密度来感受一下问题的恐怖。丑数在整数里是稀疏的100 以内还算密集到 1000 以内大概还有一百多个可越往后越稀。实际测试你会发现想要数到第 1000 个丑数从 1 开始逐个判断可能要跑好几百万次循环。n 再往上翻暴力法直接原地爆炸编程平台给你一个 n1690 的测试点基本就卡到超时。所以这道题从思路层面就排除暴力不是要你优化常数而是必须换方法论。2.2 动态规划的核心观察每个丑数都有“爸爸”暴力不行退回来从定义强推。一个丑数的质因数只有 2、3、5这意味着什么任何一个大于 1 的丑数把它除以 2、除以 3 或除以 5得到的数依然是丑数前提是它能被整除。反过来看如果已知一个小丑数把它乘以 2、3、5得到的一定是丑数。这就是生成丑数的钥匙。举例子丑数 6 可以由 2 × 3 得到丑数 8 可以由 4 × 2 得到丑数 10 可以由 2 × 5 得到丑数 12 可以由 6 × 2 得到。每个丑数都能追本溯源到一个更小的丑数乘上 2/3/5 之一。唯一的例外是 1它是整个序列的起点。既然如此我们从 dp[0]1 出发不断把已生成的丑数分别乘 2、乘 3、乘 5取其中最小的放进序列不就能从小到大生成全部丑数吗但这里立刻会出现一个工程问题你有三条“流水线”分别产出“某个丑数 × 2”、“某个丑数 × 3”、“某个丑数 × 5”的候选值。你怎么保证整体按序怎么保证不重复如果每次把所有已生成的丑数都翻一遍去乘 2/3/5那 O(n²) 就回来了本质没比暴力强多少。需要一种机制让每一步只需要看三个候选值。这就是三指针法的价值。2.3 三指针法三条流水线的比赛把 dp 数组理解成一条已经排好序的生产线。三个指针 p2、p3、p5 分别指向 dp 数组里的三个位置。约定是p2 指向“下一个要被拿去乘 2 的最小丑数”p3 和 p5 同理。每一步比较三个候选值 dp[p2]*2、dp[p3]*3、dp[p5]*5取出最小的放进 dp 末尾。为什么指针只往后走、不回头因为 dp 本身是递增的dp[0] dp[1] ... dp[i-1] 已经生成完毕。p2 从 0 开始dp[0]*22被选中成为 dp[1] 之后p2 前进到 1表示“idx0 的丑数乘 2 这个选项已经用过了下一个该拿 idx1 去乘 2”。此时 dp[1]*24和 dp[0]*33、dp[0]*55 再比赛。每一步三个指针都在各自轨道上单调走所以每条流水线每次产生的候选值只跟当前位置有关整体呈现出一种“交错推进”的状态。这个机制跟归并排序里合并三个有序数组的思路一模一样只是这里的三个数组长度不是预设的而是动态生成的。我还可以用一个生活化的类比帮你消化假设三条装配线分别给产品装 2 号、3 号、5 号零件每个装配线都有一个当前待处理的半成品位置指针。每条线每次只能前进一格三台机器同时开工每次产出最小的那个订单就出货。因为半成品从编号小的往编号大的排指针单调往后走所以每台机器下次产出的订单一定比这次大三条线之间的比较永远只需要看队首。3. 核心代码实现与参数拆解3.1 丑数判断题的代码三步除到底先写丑数判断这是基础中的基础。public boolean isUgly(int n) { if (n 0) { return false; } int[] factors {2, 3, 5}; for (int factor : factors) { while (n % factor 0) { n / factor; } } return n 1; }逻辑就三件事。第一先处理非正数——丑数必须是正整数负数、零直接返回 false这一步容易漏。第二用 2、3、5 依次去试除注意这里用的是while而不是if因为一个数可能被同一个因子多次整除比如 8 2³要连续除三次才能把因子 2 除干净。第三返回时判断最后剩下的数是不是 1。比如输入 14先除 2 得 77 除不了 2、除不了 3、也除不了 5剩下 7返回 false。Python 写法同理注意整除符号def is_ugly(n: int) - bool: if n 0: return False for factor in (2, 3, 5): while n % factor 0: n // factor return n 1这里有一个值得一提的小细节判断除法的顺序无所谓因为除以因子和顺序无关你除以 2 之后留下的数再去除 3 或 5最终结果一致。3.2 第 n 个丑数的动态规划实现三指针的舞台好戏在这里。维护一个长度为 n 的 dp 数组dp[0] 1三个指针初始都指向 0。每次生成一个丑数直到填满数组。public int nthUglyNumber(int n) { int[] dp new int[n]; dp[0] 1; int p2 0, p3 0, p5 0; for (int i 1; i n; i) { int a dp[p2] * 2; int b dp[p3] * 3; int c dp[p5] * 5; dp[i] Math.min(a, Math.min(b, c)); if (dp[i] a) { p2; } if (dp[i] b) { p3; } if (dp[i] c) { p5; } } return dp[n - 1]; }我逐段说明。dp 数组用来存放已经确认的丑数序列它天然有序。三个指针指向的位置分别代表“我希望拿它去乘 2 / 乘 3 / 乘 5 的那个丑数下标”。每一轮只做两件事从三个候选值里挑最小写进 dp然后检查这个最小值到底来自哪几条流水线把对应指针前进。注意这里if是一个个判断而不是else if这是去重的关键后面会在排查节细讲。Python 版本def nth_ugly_number(n: int) - int: dp [1] * n p2 p3 p5 0 for i in range(1, n): a, b, c dp[p2] * 2, dp[p3] * 3, dp[p5] * 5 dp[i] min(a, b, c) if dp[i] a: p2 1 if dp[i] b: p3 1 if dp[i] c: p5 1 return dp[-1]看起来短但每一行的意图都要吃透。为了更直观地理解指针如何移动我们手推一遍 n10 的过程第 1 轮三个指针都在 0候选是 2、3、5最小为 2dp[1]2p2 前进到 1。 第 2 轮候选是 dp[1]*24、dp[0]*33、dp[0]*55最小为 3dp[2]3p3 前进到 1。 第 3 轮候选是 4、6、5最小为 4dp[3]4p2 前进到 2。 第 4 轮候选是 dp[2]*26、dp[1]*36、dp[0]*55最小为 5dp[4]5p5 前进到 1。 第 5 轮候选是 6、6、10最小为 6dp[5]6p2 和 p3 同时前进到 3 和 2。 第 6 轮候选是 dp[3]*28、dp[2]*39、10最小为 8dp[6]8p2 前进到 4。 第 7 轮候选是 dp[4]*210、9、10最小为 9dp[7]9p3 前进到 3。 第 8 轮候选是 10、dp[3]*312、10最小为 10dp[8]10p2 和 p5 同时前进到 5 和 2。 第 9 轮候选是 dp[5]*212、12、dp[2]*520最小为 12dp[9]12p2 和 p3 同时前进到 6 和 4。最终 dp[9]12这就是第 10 个丑数。推完这 9 轮你会发现两个规律dp 数组严格递增没有跳过任何丑数出现重复候选值时多个指针同时前进不会把重复值写进数组。3.3 复杂度与参数边界为什么这个方案很稳时间上每轮只做三次乘法、两次比较、常数次指针更新一共执行 n-1 轮时间复杂度 O(n)。空间上一个长度 n 的 dp 数组O(n)。对比暴力遍历这是质的飞跃。对比堆方案下一节会讲同样是 O(nlogn) 变 O(n)在 n1690 时差距不明显但如果把这道题推广到“超级丑数”或更大规模三指针的优势就彻底体现出来了。还有一个细节值得留意dp 数组里存的是 int在题目常见限制下是安全的。以最经典的约束 n≤1690 为例第 1690 个丑数大概是 2123366400没有超过 int 上限 2147483647所以 int 可以安心用。但如果你在面试中遇到不限制 n 的变体或者把这道题改造为“第 m 个某类丑数”建议换个更宽的整数类型或者提前判断溢出这个我在下一节专门展开。4. 实操避坑实录这些坑我基本都踩过一轮4.1 边界条件n1、0、负数别想当然先说出题人最喜欢埋的雷n1 时第 1 个丑数就是 1循环一次都不跑直接返回 dp[n-1]dp[0]1。这个分支是在代码里天然成立的前提是你正确初始化了 dp[0]1。有些同学写循环时把for (int i 1; i n; i)错写成for (int i 0; i n; i)导致 dp[0] 被覆盖整个序列全乱。其次是 n≤0 的非法输入。虽然题目一般保证 n 是正整数但写工具函数时最好加防御直接在入口if (n 0) return -1;或抛出异常。丑数判断那道题就必须处理非正数判断一个负数或 0 永远不是丑数。这两处边界都做到位才算真正理解丑数的正整数属性。4.2 溢出int 到底够不够用我见过不止一个人把这三条乘法写成int a dp[p2] * 2写完就忘了检查溢出风险。在标准约束 n≤1690 下确实没问题但一旦题目变形比如问“第 2000 个丑数”乘积就可能顶穿 int 上限。这里有个实际工作中的好习惯如果你能提前估算最大值就把估算过程写进注释如果估算不出来就直接换long数组存 dp最后返回时再转 int代价可以忽略。估算方法其实不复杂丑数的增长速度介于指数和幂之间。最经典的经验值第 1690 个丑数约等于 2^31 以下恰好卡在 int 的边界内这是平台故意设计好的。我自己遇到过一回把 c 语言版的题改成 Java 时没注意某次把 dp 数组扩容到 2000输出全是负数排查半小时才发现是 int 溢出。从那之后我遇到这类生成型题目一律先想边界值不赌题目仁慈。4.3 去重逻辑为什么是三个 if不是 else if这是三指针法最容易写错的地方也是面试官最喜欢追问的点。很多人第一次写会写成if (dp[i] a) p2; else if (dp[i] b) p3; else if (dp[i] c) p5;看起来合理我选中的是哪个候选值就推进哪个指针。但只要候选值里有相同的数这么写就会把重复值写进 dp 数组。比如生成 6 的那一轮a 和 b 都等于 6你只能推进 p2 或 p3 其中一个另一个指针停在原地下一轮它还会再产出一个 6dp 里就出现两个 6序列被污染。正确的写法是三个独立的 if每命中一个候选值就推进对应指针。当 6 同时来自 dp[p2]*2 和 dp[p3]*3 时p2 和 p3 一起前进后续这两条流水线都不会再输出 6。记住这个原则值碰值指针就一起走。这也是三指针法相比“每轮从所有已生成丑数里找最小倍数”的一大优势——天然去重不需要额外维护集合。4.4 指针越界与逻辑验证手推样例比 debug 更快还有一个隐蔽点你有没有想过 p2、p3、p5 会不会越界毕竟 dp 数组还没填满指针会不会指到未初始化的位置我最初也担心过。分析一下就能安心每个指针最多前进到 i-1而生成 dp[i] 时只用 dp[p2]、dp[p3]、dp[p5]它们的下标最大是 i-1这些位置都已经在之前的迭代中填好值了。更重要的是因为 dp 严格递增dp[p2]*2只会越来越大不会回头所以指针不会无限停在某个位置把同一个候选值反复生成。你可以用反证法如果 p2 一直不动dp[p2]*2 就永远只是一个固定值而 dp[i] 在递增早晚会超过它那 p2 就必然有前进的理由否则下一轮最小值永远是它而它已经小于 dp[i-1] 了序列不再递增矛盾。理论归理论实操时我还是建议你手推一遍 n6 或 n10 的完整过程。我每次带人学这道题都要求先在纸上画一个三行三列的表格分别记录每轮的 p2、p3、p5 和三个候选值。推完两三组指针逻辑就再也忘不掉了。debug 永远没有手动推演来得直觉化。5. 方案对比与变体延伸别只背这一种解法5.1 堆 Set 方案更直觉但更费我知道有些同学更喜欢另一个思路用最小堆。初始把 1 放进去然后从堆里取出最小元素把它乘以 2、3、5 产生的三个数加入堆同时用 Set 去重重复 n-1 次堆顶就是第 n 个丑数。这个方案理解起来确实舒服完全就是模拟“生成—排序—去重”的直观过程。代码大致长这样public int nthUglyNumber(int n) { PriorityQueueLong heap new PriorityQueue(); SetLong seen new HashSet(); heap.offer(1L); seen.add(1L); long cur 1L; int[] factors {2, 3, 5}; for (int i 0; i n; i) { cur heap.poll(); for (int f : factors) { long next cur * f; if (seen.add(next)) { heap.offer(next); } } } return (int) cur; }这段代码有两个细节一是乘出来的结果可能瞬间爆炸必须用 long 存二是 Set 去重是必须的因为同一个数可以从不同路径生成。比如 6可以先由 2 乘 3 得到也可以由 3 乘 2 得到。但这个方案的时间复杂度是 O(nlogn)空间复杂度最坏 O(n)因为堆里会同时存在大量暂时不用的小候选值。和三指针的 O(n) 时间、O(n) 空间相比理论上确实逊一筹。不过在面试现场如果你一时想不出三指针写出堆方案也能拿大部分分数至少证明你理解了“从小丑数翻倍生成大丑数”的核心观察。我的建议是两种方案都要会写堆方案用来兜底和验证三指针作为最优解。5.2 三指针相比堆方案的核心优势三指针不只是常数级的优化它把动态规划的思想展露得很完整状态数组是“已知的丑数序列”状态转移是“三个指针各自乘积取最小”去重不是靠额外的数据结构而是靠指针的同步推进。面试官如果追问“为什么不用 Set”你至少能答出三层第一三指针保证每个丑数按统一来源生成一次不需要额外判重第二不需要维护 O(n) 规模的堆结构实际运行更快第三你能口头证明指针不会产生重复也不会遗漏。我记得某次模拟面试里对方要求我推导一下“为什么每个丑数都会被生成到”我就用反证法说任何一个丑数除 1 外都能写成另一个丑数乘以 2、3、5 的形式而那个更小的丑数一定已经在 dp 数组里所以只要生成过程完整覆盖已知丑数递归下去就能覆盖所有丑数。这是我推荐用这篇文章的标题来练手的原因——它一道题串起了“定义推导、状态设计、指针优化、去重处理”四件事。5.3 变体题超级丑数和丑数 III如果你吃透了丑数 II再去看变体会很爽。超级丑数那道题只是把 2、3、5 换成一个长度为 k 的质数数组三指针变成三个指针数组。写起来照样简洁维护 dp 数组维护一个长度和质数数组相同的指针数组每轮比较所有候选值找到最小然后遍历指针数组凡是候选值等于 min 的指针都前进。复杂度 O(nk)k 是质数个数。本质上和丑数 II 没有区别你只需要把“三个指针”抽象成“指针数组”把三次乘法抽象成循环。丑数 III 又不同了它让你求“能被 a 或 b 或 c 整除的第 n 个数”。这个场景和丑数 II 完全不同因为前者的丑数集合是离散的乘法生成后者却是筛法加容斥通常用二分答案 容斥原理来做。我不建议一口气吃太胖但你至少要知道这个系列是逐步进阶的丑数 I 是基础定义丑数 II 是 DP 生成超级丑数是指针扩展丑数 III 是数论二分。把前三道串起来刷动态规划这块的“多路归并”思想基本就焊死在脑子里了。6. 面试场景与个人经验总结说一个我自己的经历。有次为某公司的算法轮做准备把丑数 II 当作热身题第一遍写得很顺三分钟就默出了三指针代码。但对面面试官随口问了一句“你这个指针为什么不会回退”我当时愣了一下居然只回了一句“因为 dp 是递增的”。这句话本身没错但太单薄了。事后我认真把这个问题理了一遍才真正理解三指针法的本质每个指针代表一条独立流水的当前待处理位置dp 递增保证每条流水线的输出只会越来越大各自有序的三条流线归并成一条大流水线这就是多路归并。从那以后我不再背模板而是把“指针为什么单调”、“为什么不会重复”、“为什么不会遗漏”三个问题刻在脑子里。你也可以试试把每道 DP 题问透这三个问题记忆会牢固很多。还有一个更现实的经验先把丑数判断那题作为工具函数写好。很多面试官会要求你现场写 isUgly然后立刻追问 n1690 的版本。你用 1 分钟写完 isUgly再花 8 分钟把三指针代码和推演样例讲完差不多就是完美的回答节奏。如果你先讲堆方案再讲三指针优化面试官会更愿意听你的复杂度对比分析。最后提醒一句第三轮的重复候选值处理是高频考点就算你已经写出完整代码也要在口头解释里刻意强调三个独立 if 的用意这样既展示了你踩过坑也展示了你对去重本质的理解。丑数这道题虽然名字滑稽却是我和小伙伴们在准备算法面试时一致认为“性价比极高”的题目。别嫌它简单也别嫌它基础把三指针法的每一步推理都讲得出道理比做完十道模板题有价值得多。 
长河君 · 2026/10/12 19:30:46 · 阅读 1.2k 动态规划入门：丑数II三指针法详解
1. 先搞清楚这道题到底在问什么1.1 丑数的定义先说清楚什么是“丑”丑数这道题我第一次在刷题平台上看到的时候差点直接跳过名字实在太劝退了。但真正碰过之后我改变看法——这是一道把动态规划核心思想浓缩得很干净的题尤其适合用“先暴力、再优化、最后上 DP”的节奏来理解。定义先背清楚丑数是指只包含质因数 2、3、5 的正整数。质因数就是能整除这个数的质数比如 10 的质因数是 2 和 514 的质因数是 2 和 7。按这个定义6、8、10、12 都是丑数因为它们质因数全在 {2, 3, 5} 里14、21、42 不是因为混入了 7。这里有个经常让人困惑的特例数字 1 被约定为第一个丑数。为什么因为它没有任何质因数空集算作子集数学上约定俗成题目也明确规定了记下来就行后面所有推导都建立在这条约定上。这个定义看起来简单但两道题目从这里开始分岔。第一道题是“给你一个整数判断它是不是丑数”属于一次性的判断问题第二道题是“按从小到大顺序求出第 n 个丑数”属于生成序列的问题。两者难度完全不同动态规划的主角是第二道但第一道是必要的前置理解把判断逻辑吃透了第二道题里的核心思想才顺理成章。1.2 一个系列两问判断与生成先说第一问它真的有手就行。给一个整数 n不断尝试让它被 2、3、5 整除能整除就除除到不能除为止最后看剩下的是不是 1。如果是 1说明它只剩下质因数 2、3、5是丑数如果不是 1说明它含有其它质因子不是丑数。逻辑一句话就能讲清楚代码也是几行。但第二问就有点东西了。如果给你一个 n10让你手工写一下前 10 个丑数你会这么想从 1 开始逐个整数判断1 是2 是3 是4 是5 是6 是7 不是8 是9 是10 是第 10 个是 12按题目序列前 10 个丑数是 1、2、3、4、5、6、8、9、10、12。这个方法对 n10 没问题但题目要的可能 n1690这时问题来了暴力遍历的终止条件是什么你不知道第 1690 个丑数大概落在多大的整数范围内只能一边数一边往后扫。最坏情况很恐怖——丑数出现的密度随数值增大越来越低扫到几亿、几十亿都可能。这里隐藏着一个关键点判断一个数是不是丑数很容易但要在整数范围内按顺序挑出第 n 个丑数暴力法的效率完全不可控。于是你需要换一个思路——不遍历整数而是根据丑数的定义直接“生成”丑数。这就是动态规划的切入点。1.3 为什么这个系列值得认真做我后来带过几个刚入门刷题的同学发现一个普遍现象大家看到“动态规划”四个字就发怵下意识觉得要建复杂的状态转移方程、要画出二维表格。但丑数 II 是一道非常温柔的 DP 入门题它不需要你定义什么 dp[i] 代表“前 i 个物品的最大价值”也不用考虑背包容量只有一个一维数组和三根指针。思维负担小但核心味道已经齐全了你需要在多个候选方案里每次挑一个最小的同时维护好各自推进的起点。这个思想在很多更难的题里都会反复出现值得花一下午把它彻底琢磨透。2. 从暴力到动态规划思路是怎么一步步逼出来的2.1 暴力法看起来很美实际跑不动有的同学一看到第二问第一反应是我写一个 isUgly 函数然后从 1 开始逐个数判断数到第 n 个就返回。代码很简单测试小数据也能跑通过。但你想过没有这个方案连一个明确的循环上界都写不出来只能写成while (count n) num这种形式。因为不知道大丑数长在哪个数值附近只能死等。我们用密度来感受一下问题的恐怖。丑数在整数里是稀疏的100 以内还算密集到 1000 以内大概还有一百多个可越往后越稀。实际测试你会发现想要数到第 1000 个丑数从 1 开始逐个判断可能要跑好几百万次循环。n 再往上翻暴力法直接原地爆炸编程平台给你一个 n1690 的测试点基本就卡到超时。所以这道题从思路层面就排除暴力不是要你优化常数而是必须换方法论。2.2 动态规划的核心观察每个丑数都有“爸爸”暴力不行退回来从定义强推。一个丑数的质因数只有 2、3、5这意味着什么任何一个大于 1 的丑数把它除以 2、除以 3 或除以 5得到的数依然是丑数前提是它能被整除。反过来看如果已知一个小丑数把它乘以 2、3、5得到的一定是丑数。这就是生成丑数的钥匙。举例子丑数 6 可以由 2 × 3 得到丑数 8 可以由 4 × 2 得到丑数 10 可以由 2 × 5 得到丑数 12 可以由 6 × 2 得到。每个丑数都能追本溯源到一个更小的丑数乘上 2/3/5 之一。唯一的例外是 1它是整个序列的起点。既然如此我们从 dp[0]1 出发不断把已生成的丑数分别乘 2、乘 3、乘 5取其中最小的放进序列不就能从小到大生成全部丑数吗但这里立刻会出现一个工程问题你有三条“流水线”分别产出“某个丑数 × 2”、“某个丑数 × 3”、“某个丑数 × 5”的候选值。你怎么保证整体按序怎么保证不重复如果每次把所有已生成的丑数都翻一遍去乘 2/3/5那 O(n²) 就回来了本质没比暴力强多少。需要一种机制让每一步只需要看三个候选值。这就是三指针法的价值。2.3 三指针法三条流水线的比赛把 dp 数组理解成一条已经排好序的生产线。三个指针 p2、p3、p5 分别指向 dp 数组里的三个位置。约定是p2 指向“下一个要被拿去乘 2 的最小丑数”p3 和 p5 同理。每一步比较三个候选值 dp[p2]*2、dp[p3]*3、dp[p5]*5取出最小的放进 dp 末尾。为什么指针只往后走、不回头因为 dp 本身是递增的dp[0] dp[1] ... dp[i-1] 已经生成完毕。p2 从 0 开始dp[0]*22被选中成为 dp[1] 之后p2 前进到 1表示“idx0 的丑数乘 2 这个选项已经用过了下一个该拿 idx1 去乘 2”。此时 dp[1]*24和 dp[0]*33、dp[0]*55 再比赛。每一步三个指针都在各自轨道上单调走所以每条流水线每次产生的候选值只跟当前位置有关整体呈现出一种“交错推进”的状态。这个机制跟归并排序里合并三个有序数组的思路一模一样只是这里的三个数组长度不是预设的而是动态生成的。我还可以用一个生活化的类比帮你消化假设三条装配线分别给产品装 2 号、3 号、5 号零件每个装配线都有一个当前待处理的半成品位置指针。每条线每次只能前进一格三台机器同时开工每次产出最小的那个订单就出货。因为半成品从编号小的往编号大的排指针单调往后走所以每台机器下次产出的订单一定比这次大三条线之间的比较永远只需要看队首。3. 核心代码实现与参数拆解3.1 丑数判断题的代码三步除到底先写丑数判断这是基础中的基础。public boolean isUgly(int n) { if (n 0) { return false; } int[] factors {2, 3, 5}; for (int factor : factors) { while (n % factor 0) { n / factor; } } return n 1; }逻辑就三件事。第一先处理非正数——丑数必须是正整数负数、零直接返回 false这一步容易漏。第二用 2、3、5 依次去试除注意这里用的是while而不是if因为一个数可能被同一个因子多次整除比如 8 2³要连续除三次才能把因子 2 除干净。第三返回时判断最后剩下的数是不是 1。比如输入 14先除 2 得 77 除不了 2、除不了 3、也除不了 5剩下 7返回 false。Python 写法同理注意整除符号def is_ugly(n: int) - bool: if n 0: return False for factor in (2, 3, 5): while n % factor 0: n // factor return n 1这里有一个值得一提的小细节判断除法的顺序无所谓因为除以因子和顺序无关你除以 2 之后留下的数再去除 3 或 5最终结果一致。3.2 第 n 个丑数的动态规划实现三指针的舞台好戏在这里。维护一个长度为 n 的 dp 数组dp[0] 1三个指针初始都指向 0。每次生成一个丑数直到填满数组。public int nthUglyNumber(int n) { int[] dp new int[n]; dp[0] 1; int p2 0, p3 0, p5 0; for (int i 1; i n; i) { int a dp[p2] * 2; int b dp[p3] * 3; int c dp[p5] * 5; dp[i] Math.min(a, Math.min(b, c)); if (dp[i] a) { p2; } if (dp[i] b) { p3; } if (dp[i] c) { p5; } } return dp[n - 1]; }我逐段说明。dp 数组用来存放已经确认的丑数序列它天然有序。三个指针指向的位置分别代表“我希望拿它去乘 2 / 乘 3 / 乘 5 的那个丑数下标”。每一轮只做两件事从三个候选值里挑最小写进 dp然后检查这个最小值到底来自哪几条流水线把对应指针前进。注意这里if是一个个判断而不是else if这是去重的关键后面会在排查节细讲。Python 版本def nth_ugly_number(n: int) - int: dp [1] * n p2 p3 p5 0 for i in range(1, n): a, b, c dp[p2] * 2, dp[p3] * 3, dp[p5] * 5 dp[i] min(a, b, c) if dp[i] a: p2 1 if dp[i] b: p3 1 if dp[i] c: p5 1 return dp[-1]看起来短但每一行的意图都要吃透。为了更直观地理解指针如何移动我们手推一遍 n10 的过程第 1 轮三个指针都在 0候选是 2、3、5最小为 2dp[1]2p2 前进到 1。 第 2 轮候选是 dp[1]*24、dp[0]*33、dp[0]*55最小为 3dp[2]3p3 前进到 1。 第 3 轮候选是 4、6、5最小为 4dp[3]4p2 前进到 2。 第 4 轮候选是 dp[2]*26、dp[1]*36、dp[0]*55最小为 5dp[4]5p5 前进到 1。 第 5 轮候选是 6、6、10最小为 6dp[5]6p2 和 p3 同时前进到 3 和 2。 第 6 轮候选是 dp[3]*28、dp[2]*39、10最小为 8dp[6]8p2 前进到 4。 第 7 轮候选是 dp[4]*210、9、10最小为 9dp[7]9p3 前进到 3。 第 8 轮候选是 10、dp[3]*312、10最小为 10dp[8]10p2 和 p5 同时前进到 5 和 2。 第 9 轮候选是 dp[5]*212、12、dp[2]*520最小为 12dp[9]12p2 和 p3 同时前进到 6 和 4。最终 dp[9]12这就是第 10 个丑数。推完这 9 轮你会发现两个规律dp 数组严格递增没有跳过任何丑数出现重复候选值时多个指针同时前进不会把重复值写进数组。3.3 复杂度与参数边界为什么这个方案很稳时间上每轮只做三次乘法、两次比较、常数次指针更新一共执行 n-1 轮时间复杂度 O(n)。空间上一个长度 n 的 dp 数组O(n)。对比暴力遍历这是质的飞跃。对比堆方案下一节会讲同样是 O(nlogn) 变 O(n)在 n1690 时差距不明显但如果把这道题推广到“超级丑数”或更大规模三指针的优势就彻底体现出来了。还有一个细节值得留意dp 数组里存的是 int在题目常见限制下是安全的。以最经典的约束 n≤1690 为例第 1690 个丑数大概是 2123366400没有超过 int 上限 2147483647所以 int 可以安心用。但如果你在面试中遇到不限制 n 的变体或者把这道题改造为“第 m 个某类丑数”建议换个更宽的整数类型或者提前判断溢出这个我在下一节专门展开。4. 实操避坑实录这些坑我基本都踩过一轮4.1 边界条件n1、0、负数别想当然先说出题人最喜欢埋的雷n1 时第 1 个丑数就是 1循环一次都不跑直接返回 dp[n-1]dp[0]1。这个分支是在代码里天然成立的前提是你正确初始化了 dp[0]1。有些同学写循环时把for (int i 1; i n; i)错写成for (int i 0; i n; i)导致 dp[0] 被覆盖整个序列全乱。其次是 n≤0 的非法输入。虽然题目一般保证 n 是正整数但写工具函数时最好加防御直接在入口if (n 0) return -1;或抛出异常。丑数判断那道题就必须处理非正数判断一个负数或 0 永远不是丑数。这两处边界都做到位才算真正理解丑数的正整数属性。4.2 溢出int 到底够不够用我见过不止一个人把这三条乘法写成int a dp[p2] * 2写完就忘了检查溢出风险。在标准约束 n≤1690 下确实没问题但一旦题目变形比如问“第 2000 个丑数”乘积就可能顶穿 int 上限。这里有个实际工作中的好习惯如果你能提前估算最大值就把估算过程写进注释如果估算不出来就直接换long数组存 dp最后返回时再转 int代价可以忽略。估算方法其实不复杂丑数的增长速度介于指数和幂之间。最经典的经验值第 1690 个丑数约等于 2^31 以下恰好卡在 int 的边界内这是平台故意设计好的。我自己遇到过一回把 c 语言版的题改成 Java 时没注意某次把 dp 数组扩容到 2000输出全是负数排查半小时才发现是 int 溢出。从那之后我遇到这类生成型题目一律先想边界值不赌题目仁慈。4.3 去重逻辑为什么是三个 if不是 else if这是三指针法最容易写错的地方也是面试官最喜欢追问的点。很多人第一次写会写成if (dp[i] a) p2; else if (dp[i] b) p3; else if (dp[i] c) p5;看起来合理我选中的是哪个候选值就推进哪个指针。但只要候选值里有相同的数这么写就会把重复值写进 dp 数组。比如生成 6 的那一轮a 和 b 都等于 6你只能推进 p2 或 p3 其中一个另一个指针停在原地下一轮它还会再产出一个 6dp 里就出现两个 6序列被污染。正确的写法是三个独立的 if每命中一个候选值就推进对应指针。当 6 同时来自 dp[p2]*2 和 dp[p3]*3 时p2 和 p3 一起前进后续这两条流水线都不会再输出 6。记住这个原则值碰值指针就一起走。这也是三指针法相比“每轮从所有已生成丑数里找最小倍数”的一大优势——天然去重不需要额外维护集合。4.4 指针越界与逻辑验证手推样例比 debug 更快还有一个隐蔽点你有没有想过 p2、p3、p5 会不会越界毕竟 dp 数组还没填满指针会不会指到未初始化的位置我最初也担心过。分析一下就能安心每个指针最多前进到 i-1而生成 dp[i] 时只用 dp[p2]、dp[p3]、dp[p5]它们的下标最大是 i-1这些位置都已经在之前的迭代中填好值了。更重要的是因为 dp 严格递增dp[p2]*2只会越来越大不会回头所以指针不会无限停在某个位置把同一个候选值反复生成。你可以用反证法如果 p2 一直不动dp[p2]*2 就永远只是一个固定值而 dp[i] 在递增早晚会超过它那 p2 就必然有前进的理由否则下一轮最小值永远是它而它已经小于 dp[i-1] 了序列不再递增矛盾。理论归理论实操时我还是建议你手推一遍 n6 或 n10 的完整过程。我每次带人学这道题都要求先在纸上画一个三行三列的表格分别记录每轮的 p2、p3、p5 和三个候选值。推完两三组指针逻辑就再也忘不掉了。debug 永远没有手动推演来得直觉化。5. 方案对比与变体延伸别只背这一种解法5.1 堆 Set 方案更直觉但更费我知道有些同学更喜欢另一个思路用最小堆。初始把 1 放进去然后从堆里取出最小元素把它乘以 2、3、5 产生的三个数加入堆同时用 Set 去重重复 n-1 次堆顶就是第 n 个丑数。这个方案理解起来确实舒服完全就是模拟“生成—排序—去重”的直观过程。代码大致长这样public int nthUglyNumber(int n) { PriorityQueueLong heap new PriorityQueue(); SetLong seen new HashSet(); heap.offer(1L); seen.add(1L); long cur 1L; int[] factors {2, 3, 5}; for (int i 0; i n; i) { cur heap.poll(); for (int f : factors) { long next cur * f; if (seen.add(next)) { heap.offer(next); } } } return (int) cur; }这段代码有两个细节一是乘出来的结果可能瞬间爆炸必须用 long 存二是 Set 去重是必须的因为同一个数可以从不同路径生成。比如 6可以先由 2 乘 3 得到也可以由 3 乘 2 得到。但这个方案的时间复杂度是 O(nlogn)空间复杂度最坏 O(n)因为堆里会同时存在大量暂时不用的小候选值。和三指针的 O(n) 时间、O(n) 空间相比理论上确实逊一筹。不过在面试现场如果你一时想不出三指针写出堆方案也能拿大部分分数至少证明你理解了“从小丑数翻倍生成大丑数”的核心观察。我的建议是两种方案都要会写堆方案用来兜底和验证三指针作为最优解。5.2 三指针相比堆方案的核心优势三指针不只是常数级的优化它把动态规划的思想展露得很完整状态数组是“已知的丑数序列”状态转移是“三个指针各自乘积取最小”去重不是靠额外的数据结构而是靠指针的同步推进。面试官如果追问“为什么不用 Set”你至少能答出三层第一三指针保证每个丑数按统一来源生成一次不需要额外判重第二不需要维护 O(n) 规模的堆结构实际运行更快第三你能口头证明指针不会产生重复也不会遗漏。我记得某次模拟面试里对方要求我推导一下“为什么每个丑数都会被生成到”我就用反证法说任何一个丑数除 1 外都能写成另一个丑数乘以 2、3、5 的形式而那个更小的丑数一定已经在 dp 数组里所以只要生成过程完整覆盖已知丑数递归下去就能覆盖所有丑数。这是我推荐用这篇文章的标题来练手的原因——它一道题串起了“定义推导、状态设计、指针优化、去重处理”四件事。5.3 变体题超级丑数和丑数 III如果你吃透了丑数 II再去看变体会很爽。超级丑数那道题只是把 2、3、5 换成一个长度为 k 的质数数组三指针变成三个指针数组。写起来照样简洁维护 dp 数组维护一个长度和质数数组相同的指针数组每轮比较所有候选值找到最小然后遍历指针数组凡是候选值等于 min 的指针都前进。复杂度 O(nk)k 是质数个数。本质上和丑数 II 没有区别你只需要把“三个指针”抽象成“指针数组”把三次乘法抽象成循环。丑数 III 又不同了它让你求“能被 a 或 b 或 c 整除的第 n 个数”。这个场景和丑数 II 完全不同因为前者的丑数集合是离散的乘法生成后者却是筛法加容斥通常用二分答案 容斥原理来做。我不建议一口气吃太胖但你至少要知道这个系列是逐步进阶的丑数 I 是基础定义丑数 II 是 DP 生成超级丑数是指针扩展丑数 III 是数论二分。把前三道串起来刷动态规划这块的“多路归并”思想基本就焊死在脑子里了。6. 面试场景与个人经验总结说一个我自己的经历。有次为某公司的算法轮做准备把丑数 II 当作热身题第一遍写得很顺三分钟就默出了三指针代码。但对面面试官随口问了一句“你这个指针为什么不会回退”我当时愣了一下居然只回了一句“因为 dp 是递增的”。这句话本身没错但太单薄了。事后我认真把这个问题理了一遍才真正理解三指针法的本质每个指针代表一条独立流水的当前待处理位置dp 递增保证每条流水线的输出只会越来越大各自有序的三条流线归并成一条大流水线这就是多路归并。从那以后我不再背模板而是把“指针为什么单调”、“为什么不会重复”、“为什么不会遗漏”三个问题刻在脑子里。你也可以试试把每道 DP 题问透这三个问题记忆会牢固很多。还有一个更现实的经验先把丑数判断那题作为工具函数写好。很多面试官会要求你现场写 isUgly然后立刻追问 n1690 的版本。你用 1 分钟写完 isUgly再花 8 分钟把三指针代码和推演样例讲完差不多就是完美的回答节奏。如果你先讲堆方案再讲三指针优化面试官会更愿意听你的复杂度对比分析。最后提醒一句第三轮的重复候选值处理是高频考点就算你已经写出完整代码也要在口头解释里刻意强调三个独立 if 的用意这样既展示了你踩过坑也展示了你对去重本质的理解。丑数这道题虽然名字滑稽却是我和小伙伴们在准备算法面试时一致认为“性价比极高”的题目。别嫌它简单也别嫌它基础把三指针法的每一步推理都讲得出道理比做完十道模板题有价值得多。