企业官网建设流程全解析

思路：动态规划 + 多指针

维护一个数组 dp，dp[i] 表示第 i+1 个超级丑数，dp[0] = 1。

对每个质数 primes[j] 维护一个指针 idx[j]，表示它下一个要乘的 dp 下标。每一轮取所有 dp[idx[j]] * primes[j] 中的最小值作为新的超级丑数，并把所有等于该最小值的指针向后移动一位（用 if 而非 else if 来去重）。

Java 实现

classSolution{publicintnthSuperUglyNumber(intn,int[]primes){intk=primes.length;int[]dp=newint[n];dp[0]=1;int[]idx=newint[k];// 每个质数对应的指针for(inti=1;i<n;i++){longmin=Long.MAX_VALUE;// 找本轮最小值for(intj=0;j<k;j++){min=Math.min(min,(long)dp[idx[j]]*primes[j]);}dp[i]=(int)min;// 所有产生该最小值的质数指针都前移（去重）for(intj=0;j<k;j++){if((long)dp[idx[j]]*primes[j]==min){idx[j]++;}}}returndp[n-1];}}

关键点

1. 去重：多个质数可能产生相同的丑数（如 2×3 和 3×2），所以要用 if 循环把所有产生该值的指针都 +1，不能用 else if。
2. 防溢出：dp[idx[j]] * primes[j] 可能超过 int，先转成 long 再比较；因为题目保证第 n 个超级丑数在 int 范围内，最后转回 int 是安全的。
3. 复杂度：时间 O(n·k)，空间 O(n + k)。

附：优先队列写法（更直观，但内存更大）

classSolution{publicintnthSuperUglyNumber(intn,int[]primes){PriorityQueue<Long>pq=newPriorityQueue<>();pq.offer(1L);longcur=1;for(inti=0;i<n;i++){cur=pq.poll();// 弹出重复值while(!pq.isEmpty()&&pq.peek()==cur){pq.poll();}for(intp:primes){pq.offer(cur*p);}}return(int)cur;}}

优先队列写法可能因堆中元素过多而较慢或超内存，推荐使用多指针 DP 解法。