leetcode
leetcode 2851 ~ 2900
剧情触发时间

剧情触发时间

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 181 ms, 内存: 71.8 MB


/*
 * 题目思路:
 * 1. 初始化三种属性 C, R, H 为 0。
 * 2. 使用流的方式累加每一天的属性值。
 * 3. 对于每个剧情的触发条件,检查当前的 C, R, H 是否满足要求,如果满足则记录触发时间。
 * 4. 如果遍历完所有 increase 后还有未触发的剧情,则记录为 -1。
 */
import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int[] getTriggerTime(int[][] increase, int[][] requirements) {
        int n = increase.length;
        int m = requirements.length;
        int[] result = new int[m];
        int[] C = new int[n + 1];
        int[] R = new int[n + 1];
        int[] H = new int[n + 1];

        // 初始化第 0 天
        C[0] = 0;
        R[0] = 0;
        H[0] = 0;

        // 使用流累加每一天的属性值
        IntStream.range(0, n).forEach(i -> {
            C[i + 1] = C[i] + increase[i][0];
            R[i + 1] = R[i] + increase[i][1];
            H[i + 1] = H[i] + increase[i][2];
        });

        // 检查每个剧情的触发时间
        Arrays.fill(result, -1);
        IntStream.range(0, m).forEach(j -> {
            IntStream.range(0, n + 1).filter(i -> result[j] == -1)
                    .filter(i -> C[i] >= requirements[j][0] && R[i] >= requirements[j][1] && H[i] >= requirements[j][2])
                    .findFirst().ifPresent(i -> result[j] = i);
        });

        return result;
    }
}

解释

方法:

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

时间复杂度:

O(n + m)

空间复杂度:

O(sum(increase))

代码细节讲解

🦆
为什么在更新属性值字典时,选择将所有中间值都存储下来,而不是仅存储每天结束时的总和?
在更新属性值字典时选择存储所有中间值的原因是为了能够精确地查找到达每个特定值的最早天数。如果只存储每天结束时的总和,我们只能知道每天结束时的属性值,但不能确定在一天中的哪个时刻首次达到了某个属性值。例如,如果某一天文明等级从10增加到15,仅存储总和我们只知道第二天的文明等级是15,但是具体达到11, 12, 13, 14的时间则无法确定。存储所有中间值可以让我们快速准确地对应到每个剧情触发条件,避免了额外的计算或遍历,提高了查询效率。
🦆
在代码中,使用了999999作为默认值来标记不可触发的剧情,这种方法是否是最有效的,还有没有其他更好的方法来处理这种情况?
使用999999作为默认值是一种简单直观的方法来标记不可触发的剧情,但它依赖于假设剧情触发的天数不会达到这个数值,这可能在某些极端情况下不是最佳选择。更稳健的方法包括使用`None`或特定的标志值,这样可以明确表示未达到的状态,而无需担心数值上的限制。在实际应用中,可以通过检查是否为`None`来决定剧情是否触发,这样代码的可读性和健壮性都会提高。
🦆
如果输入的`requirements`数组非常大,查找每个属性值是否存在于字典中的效率是否会成为性能瓶颈?
如果`requirements`数组非常大,每次查找属性值是否存在于字典中确实可能成为性能瓶颈。虽然字典查找通常是O(1)操作,但大量的查找会累积显著的计算时间。此外,如果`requirements`中的值远大于字典中的键,则许多查找将返回默认值,这些无效查找会浪费计算资源。为了优化性能,可以考虑预处理和优化数据结构,例如使用有序的数据结构(如平衡树)来存储达到的属性值和对应天数,并利用二分查找来确定最接近的有效天数,这可能会在保持查找效率的同时减少不必要的查找操作。

相关问题