编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1是丑数。n不超过1690。
**难度**: Medium
**标签**: 堆、 数学、 动态规划、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：164 ms, 在所有 Python3 提交中击败了77.50% 的用户
内存消耗：13.6 MB, 在所有 Python3 提交中击败了91.44% 的用户
解题思路：
三指针，参考的官方解题思路：https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode/
"""
class Solution:
def nthUglyNumber(self, n: int) -> int:
p2, p3, p5 = 0, 0, 0
dp = [1 for _ in range(n)]
for i in range(1, n):
min_ = min(2*dp[p2], 3*dp[p3], 5*dp[p5])
dp[i] = min_
if dp[p2] * 2 == min_:
p2 += 1
if dp[p3] * 3 == min_:
p3 += 1
if dp[p5] * 5 == min_:
p5 += 1
return dp[-1]