思路动态规划 三指针丑数序列1, 2, 3, 4, 5, 6, 8, 10, 12, …每个丑数都可以由之前的某个丑数乘以 2、3 或 5 得到。维护三个指针 p2, p3, p5分别表示下一个要乘以 2、3、5 的丑数下标。每次取min(dp[p2]*2,dp[p3]*3,dp[p5]*5)作为下一个丑数并移动对应的指针。Java 实现classSolution{publicintnthUglyNumber(intn){int[]dpnewint[n];dp[0]1;intp20,p30,p50;for(inti1;in;i){longnext2(long)dp[p2]*2;longnext3(long)dp[p3]*3;longnext5(long)dp[p5]*5;longnextMath.min(next2,Math.min(next3,next5));dp[i](int)next;// 注意用 if 而不是 else if避免重复值漏掉指针移动if(nextnext2)p2;if(nextnext3)p3;if(nextnext5)p5;}returndp[n-1];}}复杂度分析· 时间复杂度O(n)每个丑数只生成一次。· 空间复杂度O(n)dp 数组存储结果。关键点三指针含义p2 指向的丑数乘以 2 是当前最小的候选值p3、p5 同理。去重例如 6 2 * 3 3 * 2所以当 next 同时等于 next2 和 next3 时两个指针都要后移因此必须用三个独立的 if。防止溢出虽然 n 1690 时结果在 int 范围内但中间乘法可能越界使用 long 更安全。