动态规划 O(n)

新的丑数一定是由旧的丑数乘以丑数的质因数得到的。所以我们维护三个指针i,j,k，每次添加进去一个当前计算出来个三个丑数的最小的一个，并且是谁计算的，谁指针就后移一位。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n, 1);
        int i = 0, j = 0, k = 0, index = 1;
        while(index < n) {
            dp[index] = min({dp[i]*2, dp[j]*3, dp[k]*5});
            if(dp[index] == dp[i]*2) ++i;
            if(dp[index] == dp[j]*3) ++j;
            if(dp[index] == dp[k]*5) ++k;
            ++index;
        }
        return dp.back();
    }
};