剧情触发时间
难度:
标签:
题目描述
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))
代码细节讲解
🦆
为什么在更新属性值字典时,选择将所有中间值都存储下来,而不是仅存储每天结束时的总和?
▷🦆
在代码中,使用了999999作为默认值来标记不可触发的剧情,这种方法是否是最有效的,还有没有其他更好的方法来处理这种情况?
▷🦆
如果输入的`requirements`数组非常大,查找每个属性值是否存在于字典中的效率是否会成为性能瓶颈?
▷