不可能得到的最短骰子序列

难度: Hard

给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。

请你返回无法从 rolls 中得到的最短骰子子序列的长度。

扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。

注意，子序列只需要保持在原数组中的顺序，不需要连续。

示例 1：

输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4
输出：3
解释：所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。
所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。
子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。
还有别的子序列也无法从原数组中得到。

示例 2：

输入：rolls = [1,1,2,2], k = 2
输出：2
解释：所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。
子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。
还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。

示例 3：

输入：rolls = [1,1,3,2,2,2,3,3], k = 4
输出：1
解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。
还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。

提示：

n == rolls.length
1 <= n <= 10⁵
1 <= rolls[i] <= k <= 10⁵

Submission

运行时间: 66 ms

内存: 23.9 MB

class Solution:
    def shortestSequence(self, rolls: List[int], k: int) -> int:
        mask = [0] * (k + 1)
        ans, left = 1, k
        for roll in rolls:
            if mask[roll] < ans:
                mask[roll] = ans
                left -= 1
                if left == 0:
                    left = k
                    ans += 1
        return ans

Explain

这个题解使用了一种贪心的策略来找到无法从rolls中得到的最短骰子子序列的长度。它维护了一个数组mask，用于记录每个数字最后一次出现在哪个子序列中。变量ans表示当前正在构建的子序列的长度，而left表示在当前子序列中还没有出现的数字的个数。遍历rolls数组，如果当前数字roll在mask中的值小于ans，说明它在当前子序列中还没有出现过，将mask[roll]更新为ans，并将left减一。如果left变为0，说明当前子序列中已经包含了所有1到k的数字，因此需要开始构建新的子序列，将ans加一并重置left为k。

时间复杂度: O(n)

空间复杂度: O(k)

class Solution:
    def shortestSequence(self, rolls: List[int], k: int) -> int:
        mask = [0] * (k + 1)  # 初始化mask数组，记录每个数字最后出现在哪个子序列中
        ans, left = 1, k  # ans表示当前子序列的长度，left表示当前子序列中还未出现的数字个数
        for roll in rolls:
            if mask[roll] < ans:  # 如果当前数字在当前子序列中还未出现
                mask[roll] = ans  # 更新mask，表示该数字已出现在当前子序列中
                left -= 1  # 减少未出现的数字个数
                if left == 0:  # 如果当前子序列中已包含所有数字
                    left = k  # 重置left为k，准备构建新的子序列
                    ans += 1  # 增加子序列的长度
        return ans  # 返回无法从rolls中得到的最短骰子子序列的长度

Explore

在这个算法中，mask数组的角色是用来记录每个数字最后一次出现在哪个子序列中。具体来说，mask的索引表示骰子的面数（例如，索引1代表骰子面为1），而该索引的值表示该面数最后出现在第几个子序列中。选择使用mask数组的原因是为了高效地跟踪和更新每个数字的出现状态。通过检查一个数字的mask值与当前子序列的长度的比较，我们可以快速判断出一个数字是否已经在当前构建的子序列中出现过，从而决定是否需要开始一个新的子序列。这种方法避免了使用复杂的数据结构，简化了实现，并提高了算法的执行效率。

当一个数字第一次在当前子序列中出现时，将其在mask数组中的值更新为当前子序列的长度ans，是为了标记这个数字已经被包括在当前子序列中。这样做的目的是为了在后续的遍历中判断一个数字是否已经在这个子序列中出现过。如果一个数字的mask值小于当前的子序列长度ans，说明这个数字在当前子序列中尚未出现。这样可以确保每次当所有可能的数字都至少出现一次时，我们才开始新的子序列，确保子序列的构建是正确和完整的。

在遍历结束后直接返回ans作为结果，确实意味着根据当前算法逻辑，所有可能的子序列长度都已经被检查过。算法通过不断更新子序列长度来确保每种数字的出现至少被记录了一次，然后开始一个新的子序列。这种方法保证了只要存在一个无法从rolls中完整构建的子序列，它就会在某个点被识别，因此返回的ans代表的是无法从rolls中得到的最短子序列的长度。因此，根据这种算法策略，不存在未被检测到的更短的无法从rolls中得到的子序列。