暴力枚举效率低因丑数稀疏，需检查大量非丑数，时间复杂度高；三指针法利用丑数由2/3/5乘得的结构性，动态生成，避免重复与遗漏，时间O(N)、空间O(N)。
为什么不能用暴力枚举判断每个数是否为丑数
暴力方法是写一个 isUgly() 函数，对每个正整数调用它，直到累计找到 N 个丑数。但这个做法在 N > 1000 时就会明显变慢——因为越往后，丑数越稀疏，比如第 1690 个丑数是 2123366400，而你得检查中间所有非丑数（含大量 7、11、13 等因子的数），时间复杂度接近 O(N × log M)，M 是第 N 个丑数值，实际运行可能超时。
关键问题在于：你不是在「筛选」，而是在「盲猜」。丑数集合本身有强结构性，应该利用生成逻辑，而非判定逻辑。
三指针法（动态规划）是怎么工作的
丑数序列从 1 开始，之后每个新丑数必然是已有丑数乘以 2、3 或 5 得到的最小值。用三个指针 i2、i3、i5 分别指向「下一个将要乘以 2/3/5 的丑数下标」，初始都为 0（对应 dp[0] == 1）。
每轮计算：
– next2 = dp[i2] * 2
– next3 = dp[i3] * 3
– next5 = dp[i5] * 5
取三者最小值作为 dp[i]，然后把所有等于该最小值的指针都 +1（注意：是「所有」，不是只加一个，否则会重复）。
示例（前 10 个）：dp = [1]，i2=i3=i5=0
→ next2=2, next3=3, next5=5 → min=2 → dp=[1,2]，i2=1（其余不变）
→ next2=4, next3=3, next5=5 → min=3 → dp=[1,2,3]，i3=1
→ next2=4, next3=6, next5=5 → min=4 → dp=[1,2,3,4]，i2=2
→ next2=6, next3=6, next5=5 → min=5 → dp=[1,2,3,4,5]，i5=1
→ next2=6, next3=6, next5=10 → min=6 → 此时 next2==next3==6，所以 i2 和 i3 都 +1
代码实现要注意的三个细节
容易出错的地方不在算法主干，而在边界和更新逻辑：
-
dp数组长度必须为 N，索引从 0 到 N−1，返回dp[N-1]，不是dp[N] - 三个候选值必须用
long long或等效类型暂存，否则dp[i2] * 2在 N 较大时（如 N=1690）会溢出int - 当多个候选值相等时（如 6 = 2×3 = 3×2），对应的所有指针都要推进，否则后续会重复生成相同丑数
有没有更省空间的写法
标准三指针法需要 O(N) 空间存整个 dp 数组，但如果你只需要第 N 个，不需输出全部序列，可以只维护三个指针和上一个生成的丑数值，用滚动变量替代数组。不过实际中几乎没人这么干——因为 N 通常不大（LeetCode 最大 1690），且数组方式逻辑清晰、不易错；强行省那几 KB 内存反而增加理解成本和出错概率。
真正值得留意的是：这个问题的「N」往往隐含上限，如果题目要求支持 N=1e6，那就要考虑预计算 + 静态缓存，而不是每次 new 一个 vector —— 但那是工程优化，不是算法核心。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
