<p>An <strong>ugly number</strong> is a positive integer whose prime factors are limited to <code>2</code>, <code>3</code>, and <code>5</code>.</p>

<p>Given an integer <code>n</code>, return <em>the</em> <code>n<sup>th</sup></code> <em><strong>ugly number</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 12
<strong>Explanation:</strong> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1690</code></li>
</ul>

// use priority_queue to get min and second min
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n <= 3)
            return n;
        vector<long long> Uglys{1, 2, 3};
        vector<long long> Us{1, 2, 3};
        vector<long long> ts{5, 4, 6};
        vector<int> Vs{3, 1, 1};
        
        priority_queue<long long, vector<long long>, greater<long long>> Ts{};
        Ts.push(5);
        Ts.push(4);
        Ts.push(6);

        int next_Uglys = 3;
        while (true)
        {
            long long next = Ts.top();

            Uglys.push_back(next);
            if (Uglys.size() >= n)
                break;

            while (Ts.top() == next)
                Ts.pop();
            
            if (Ts.top() > Uglys[next_Uglys] * 2)
            {
                Us.push_back(Uglys[next_Uglys++]);
                Vs.push_back(0);
                int pos = Us.size() - 1;
                ts.push_back(getTs(Us[pos], Vs[pos]));
                if (next < ts[pos])     // if equal, ts[po] will be replaced later
                    Ts.push(ts[pos]);
            }
            for (int pos = 0; pos < ts.size(); pos++)
            {
                bool get_ts = false;
                while (ts[pos] == next)
                {
                    if (Vs[pos] == 3)
                    {
                        Us[pos] = Uglys[next_Uglys++];
                        Vs[pos] = 0;
                    }
                    ts[pos] = getTs(Us[pos], Vs[pos]);
                    get_ts = true;
                }
                if (get_ts)
                {
                    Ts.push(ts[pos]);
                }
            }
        }
        return Uglys[n - 1];
    }
    
    long long getTs(long long U, int &V)
    {
        V++;
        switch (V)
        {
            case 1:
                return U * 2;
            case 2:
                return U * 3;
            case 3:
                return U * 5;
        }
        return 0;
    }
};
20503