超级丑数

丑数越往后越稀疏（比如 25 之后下一个可能跳到 27、30），一个个枚举判断会浪费大量功夫在「不是丑数」的数上。我们想只生成丑数本身。

1×2=2、1×3=3、2×2=4……所有丑数都长在「已有丑数」上。于是我们维护一个有序丑数数组，每次从「旧丑数×质数」的候选里挑最小的接到队尾。

primes=[2,3,5] 就开 3 个指针 p0/p1/p2，各自候选 = primes[j] × ugly[ptr[j]]。三路候选取最小，谁被选中谁的指针就往后挪一格。下面一步步演。

起手 · 第 1 个丑数恒为 1：丑数数组第一格永远是 1（任何质数都不含也算）。三个指针 p0/p1/p2 全指向 ugly[0]=1，于是右边候选是 2、3、5。「·」是还没生成的格子。

第 2 个 · 三候选里挑最小：右边三路候选 2/3/5，最小的是 2（被高亮那行），它由 p0 贡献。下一帧把它接到队尾。

第 2 个 · 写队尾并推进 p0：2 接到队尾成 ugly[1]。是 p0 贡献的，p0 往后挪一格指向 ugly[1]=2，它的新候选变成 2×2=4。p1/p2 没动。

第 3 个 · 挑最小：p0 候选已变 4，现在候选 4/3/5，最小是 3（p1 贡献）。

第 3 个 · 写队尾并推进 p1：3 接到队尾成 ugly[2]，p1 挪到 ugly[1]，新候选 3×2=6。

第 4 个 · 挑最小：候选 4/6/5，最小 4（p0 贡献）。

第 4 个 · 写队尾并推进 p0：4 入队成 ugly[3]，p0 挪到 ugly[2]，候选变 2×3=6。注意 p0、p1 的候选现在都等于 6——下面要小心。

第 5 个 · 挑最小：候选 6/6/5，最小 5（p2 第一次出手）。

第 5 个 · 写队尾并推进 p2：5 入队成 ugly[4]，p2 挪到 ugly[1]，候选 5×2=10。

现在 p0、p1 候选都是 6。如果只把其中一个指针往后挪，下一步另一个还会再吐一个 6 → 数组里出现两个 6，重复了。正确做法：凡是候选 == 当前最小值的指针，全部一起推进。

第 6 个 · 挑最小（两路并列！）：候选 6/6/10，最小是 6，但 p0、p1 候选都等于 6！下一帧写一次 6，且两个指针都要推进，否则会重复。

第 6 个 · 写一次，p0、p1 同时推进：最小值 6 只写一次到 ugly[5]，但 p0、p1 两个指针都往后挪：p0→2×4=8，p1→3×3=9。这样下一步就不会再重复吐 6 了——去重的关键就在这。

第 7 个 · 挑最小：候选 8/9/10，最小 8（p0 贡献）。注意序列里没有 7——7 不在 primes 里，没有任何候选等于 7。

第 7 个 · 写队尾并推进 p0：8 入队成 ugly[6]，p0 挪到 ugly[4]=5，候选 2×5=10。

第 8 个 · 挑最小：候选 10/9/10，最小 9（p1 贡献）。两个 10 这次没被选中，它们的指针不动。

第 8 个 · 写队尾并推进 p1：9 入队成 ugly[7]，p1 挪到 ugly[3]=4，候选 3×4=12。

第 9 个 · 挑最小（又两路并列）：候选 10/12/10，最小 10，p0、p2 又一次并列！下一帧写一次 10，两路指针一起推进。

第 9 个 · 写一次，p0、p2 同时推进：只写一次 10 到 ugly[8]，p0、p2 都推进：p0→2×6=12，p2→5×3=15。又一次去重成功。

第 10 个 · 最后一格，答案出炉：候选 12/12/15，最小 12（p0、p1 并列，都推进）。12 填进最后一格 ugly[9]。数组满了，第 10 个超级丑数就是 12，和示例答案对上！整条序列一个不重、一个不漏地造了出来。

回看 · 三指针扫过的轨迹：三个指针各自从头单向前进、永不回退，整体像三条拉链共同合并出一条有序序列。这正是「多路归并」的思想：每路有序，取队头最小逐个吐出。

k 是质数个数。每生成一个丑数，扫一遍 k 路候选取最小、推进若干指针，共 n 个 → O(n·k)。只造丑数、不碰非丑数，干净利落。

雷区实演 · 漏推并列指针 → 重复：假设第 6 步只推进了 p0（候选 6→8），p1 的候选仍停在 6。下一步取最小又会吐出一个 6 → 序列变成 …,6,6,… 重复了。所以并列最小必须全部推进。

边界三连：n=1 时直接返回 ugly[0]=1；只有一个质数时退化成「该质数的幂序列」，多指针逻辑依然成立。

面试追问：把「它就是丑数 II 的推广」和「并列同值要全推进」两句讲透，再补一句堆优化的同值陷阱，是这题的加分点。