剧情触发时间

难度: Medium

在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（C），资源储备（R）以及人口数量（H）。在游戏开始时（第 0 天），三种属性的值均为 0。

随着游戏进程的进行，每一天玩家的三种属性都会对应增加，我们用一个二维数组 increase 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组，例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2。

所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件 c[i], r[i], h[i]，如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，则剧情会被触发。

根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1 。

示例 1：

输入： increase = [[2,8,4],[2,5,0],[10,9,8]] requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]

输出: [2,-1,3,-1]

解释：

初始时，C = 0，R = 0，H = 0

第 1 天，C = 2，R = 8，H = 4

第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0

第 3 天，C = 14，R = 22，H = 12，此时触发剧情 2

剧情 1 和 3 无法触发。

示例 2：

输入： increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]] requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]

输出: [-1,4,3,3,3]

示例 3：

输入： increase = [[1,1,1]] requirements = [[0,0,0]]

输出: [0]

限制：

1 <= increase.length <= 10000
1 <= requirements.length <= 100000
0 <= increase[i] <= 10
0 <= requirements[i] <= 100000

Submission

运行时间: 181 ms

内存: 71.8 MB

class Solution:
    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:
        C = {0:0}
        R = {0:0}
        H = {0:0}

        c = r = h = 0
        for day, (ci, ri, hi) in enumerate(increase):
            for i in range(c+1, c+ci+1):
                C[i] = day + 1
            for i in range(r+1, r+ri+1):
                R[i] = day + 1
            for i in range(h+1, h+hi+1):
                H[i] = day + 1
            c += ci
            r += ri 
            h += hi 

        # print(C)
        # print(R)
        # print(H)
        ans = []
        for cr, rr, hr in requirements:
            d = max(C.get(cr, 999999), R.get(rr, 999999), H.get(hr, 999999))
            ans.append(-1 if d == 999999 else d)
        return ans

Explain

该题解采用了映射方法来追踪每种属性值首次达到某个数字的天数。首先，使用三个字典 C、R 和 H 分别记录文明等级、资源储备和人口数量每达到一个新的值的最早天数。随着天数的增加，每天的增长通过 `increase` 数组给出，更新这三个字典，以便快速查找任何给定属性值可以在哪一天达到。在处理 `requirements` 数组时，对于每一组剧情触发条件，查找三个属性所需的最低值是否存在于对应的字典中，并取这三个值的最大索引（即最晚的天数），因为剧情触发需要三个条件同时满足。如果任一属性的要求无法满足，则该剧情不可触发，返回 -1。

时间复杂度: O(n + m)

空间复杂度: O(sum(increase))

class Solution:
    def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:
        C = {0:0}  # 初始化文明等级字典
        R = {0:0}  # 初始化资源储备字典
        H = {0:0}  # 初始化人口数量字典

        c = r = h = 0  # 初始属性值
        for day, (ci, ri, hi) in enumerate(increase):  # 遍历每天的属性增加值
            for i in range(c+1, c+ci+1):
                C[i] = day + 1  # 更新达到每个文明等级的最早天数
            for i in range(r+1, r+ri+1):
                R[i] = day + 1  # 更新达到每个资源储备的最早天数
            for i in range(h+1, h+hi+1):
                H[i] = day + 1  # 更新达到每个人口数量的最早天数
            c += ci
            r += ri
            h += hi

        ans = []
        for cr, rr, hr in requirements:  # 检查每个剧情触发条件
            d = max(C.get(cr, 999999), R.get(rr, 999999), H.get(hr, 999999))  # 查找每个条件的触发天数，取最晚的一天
            ans.append(-1 if d == 999999 else d)  # 如果任一条件未被满足，则返回 -1
        return ans

Explore

在更新属性值字典时选择存储所有中间值的原因是为了能够精确地查找到达每个特定值的最早天数。如果只存储每天结束时的总和，我们只能知道每天结束时的属性值，但不能确定在一天中的哪个时刻首次达到了某个属性值。例如，如果某一天文明等级从10增加到15，仅存储总和我们只知道第二天的文明等级是15，但是具体达到11, 12, 13, 14的时间则无法确定。存储所有中间值可以让我们快速准确地对应到每个剧情触发条件，避免了额外的计算或遍历，提高了查询效率。

使用999999作为默认值是一种简单直观的方法来标记不可触发的剧情，但它依赖于假设剧情触发的天数不会达到这个数值，这可能在某些极端情况下不是最佳选择。更稳健的方法包括使用`None`或特定的标志值，这样可以明确表示未达到的状态，而无需担心数值上的限制。在实际应用中，可以通过检查是否为`None`来决定剧情是否触发，这样代码的可读性和健壮性都会提高。

如果`requirements`数组非常大，每次查找属性值是否存在于字典中确实可能成为性能瓶颈。虽然字典查找通常是O(1)操作，但大量的查找会累积显著的计算时间。此外，如果`requirements`中的值远大于字典中的键，则许多查找将返回默认值，这些无效查找会浪费计算资源。为了优化性能，可以考虑预处理和优化数据结构，例如使用有序的数据结构（如平衡树）来存储达到的属性值和对应天数，并利用二分查找来确定最接近的有效天数，这可能会在保持查找效率的同时减少不必要的查找操作。