第 n 个丑数：从暴力枚举到动态规划 + 多指针
在算法训练与工程实现中，'以最小代价生成目标序列' 是一类非常典型的优化场景。第 n 个丑数问题看似简单，却能很好地体现从暴力思路到线性复杂度、从正确性到效率的完整思考路径，也能映射出实际工程中避免无效计算、精准控制状态、减少冗余操作的设计思想。本文以朴素推导为主，不做过度包装，专注思路演进与细节理解。
一、问题回顾
给定整数 n，返回第 n 个丑数。
丑数定义：
- 只包含质因数 2、3、5 的正整数；
- 1 是第一个丑数。
前几项丑数：
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …
要求：在 n 较大时（如 10³、10⁴、10⁵ 级别）仍能稳定、高效地给出结果。
二、最直观思路：暴力判断（从正确性出发）
最容易想到的做法是：
- 从 1 开始逐个遍历整数；
- 对每个数，判断它是否只由 2、3、5 因子构成；
- 统计是丑数的个数，直到找到第 n 个。
核心判断逻辑（伪代码思路）
bool isUgly(int x) { if (x <= 0) return false; while (x % 2 == 0) x /= 2; while (x % 3 == 0) x /= 3; while (x % 5 == 0) x /= 5; return x == 1; }
存在的问题
- 绝大多数数字都不是丑数，会做大量无效除法与判断；
- 数字越大，非丑数密度越高，浪费的计算量越大；
- 时间复杂度不可控，本质是用'筛选'代替'生成'，在大规模场景下不具备实用价值。
这也是很多算法题的共同特点：能做对 ≠ 能用，尤其在对延迟、吞吐量有要求的场景中，必须从源头减少无效操作。
三、从定义反推：丑数的生成性质
回到定义：
丑数只由 2、3、5 相乘得到，且 1 是基础丑数。
可以直接得出一条关键性质：
所有丑数，都可以由更小的丑数 ×2 / ×3 / ×5 得到。
这意味着：
- 我们不需要去判断任何一个数是不是丑数；
- 只需要从已有的丑数里生成下一个。
思路立刻升级：从'遍历 + 判断'变成'定向生成 + 有序维护'。
但随之而来两个问题：
- 生成的数会乱序，无法直接取第 n 个；
- 不同路径会生成相同数字（如 2×3=6，3×2=6），存在重复。
