给定两条按照时间戳严格递增排列的稀疏时间序列 A 和 B，其中每个数据点表示从该时间戳开始，该序列的当前值发生变化，并持续保持该值直到下一次变化。每个数据点的格式为 [time, value]。要求将两条时间序列按照时间顺序进行合并，并生成一条新的时间序列，使得每个时间点的输出值等于 A 和 B 在该时间点的当前有效值之和。如果某条序列在最小时间戳之前没有事件，则其初始值默认为 0。当某条序列已经处理完毕时，其最后一个状态仍然持续有效，因此另一条序列后续发生变化时，仍需要使用该最终状态计算合并值。输出结果需要去除冗余事件，只有当两条序列当前值之和相对于上一次输出真正发生变化时，才记录新的时间点。如果 A 和 B 在相同时间戳同时发生变化，则必须在该时间点同时更新两个序列的状态，并只产生一次合并结果，不能产生中间状态或重复时间点。两条输入序列长度分别为 n 和 m，时间戳均已按照递增顺序排列。
示例 1：
输入：
A = [(1, 2), (3, 5), (7, 0)]
B = [(2, 3), (6, 1), (12, 0)]
输出：
[(1, 2), (2, 5), (3, 8), (6, 6), (7, 1), (12, 0)]
解释：
1：只有 A 发生变化，当前值为 2，所以结果为 2。2：B 变为 3，当前 A = 2，因此结果为 2 + 3 = 5。3：A 变为 5，因此结果为 5 + 3 = 8。6：B 变为 1，因此结果为 5 + 1 = 6。7：A 变为 0，因此结果为 0 + 1 = 1。12：B 变为 0，因此结果为 0 + 0 = 0。示例 2：
输入：
A = [(1, 2), (5, 0)]
B = [(1, 3), (5, 0)]
输出：
[(1, 5), (5, 0)]
解释：
在时间 1，A 和 B 同时发生变化，因此必须同时更新两个状态，然后只输出一次 (1, 5)。
在时间 5，两个序列同时变为 0，最终合并值变为 0，因此只输出一次 (5, 0)。
示例 3：
输入：
A = [(1, 5)]
B = [(2, 3), (4, 0)]
输出：
[(1, 5), (2, 8), (4, 5)]
解释：
A 在时间 1 后一直保持 5。即使 A 已经没有更多事件，仍然必须继续处理 B 的后续事件。
时间 2：B 变为 3，结果为 5 + 3 = 8。
时间 4：B 变为 0，结果为 5 + 0 = 5。
pA 和 pB 按照时间戳从小到大扫描两条有序时间序列，同时维护 A 和 B 当前有效的状态值。pA = 0、pB = 0，分别指向两条序列当前待处理事件。valA = 0、valB = 0，表示两条序列当前有效值。pA < n 或 pB < m 时继续处理。A[pA][0] 和 B[pB][0]。combinedVal = valA + valB。combinedVal 与上一次输出值不同的时候，才将当前 [time, combinedVal] 加入结果。A 和 B 同时为空时返回空结果。K 条有序时间序列，可以使用 Min-Heap 进行 K-way Merge。N 的 K 路输入，时间复杂度可以达到 O(N log K)，辅助空间为 O(K)。k 为最终输出事件数量，最坏情况下为 O(n + m)。import java.util.ArrayList;
import java.util.List;
public class TimeSeriesMerger {
public static List<int[]> mergeTimeSeries(int[][] a, int[][] b) {
List<int[]> result = new ArrayList<>(); // 保存最终合并后的时间序列
if (a == null && b == null) { // 两条序列都为空时直接返回空结果
return result; // 返回空列表
}
if (a == null || a.length == 0) { // A 为空时只处理 B
return deduplicateAndCopy(b); // 返回 B 的去重结果
}
if (b == null || b.length == 0) { // B 为空时只处理 A
return deduplicateAndCopy(a); // 返回 A 的去重结果
}
int pA = 0; // 指向 A 当前未处理的事件
int pB = 0; // 指向 B 当前未处理的事件
int valA = 0; // A 当前有效值
int valB = 0; // B 当前有效值
int lastEmittedVal = Integer.MIN_VALUE; // 保存上一次输出的合并值
while (pA < a.length || pB < b.length) { // 只要任意一条序列仍有事件就继续
int currentTime; // 保存当前处理的时间戳
if (pA < a.length && pB < b.length) { // 两条序列都有未处理事件
int timeA = a[pA][0]; // 获取 A 当前事件的时间
int timeB = b[pB][0]; // 获取 B 当前事件的时间
if (timeA < timeB) { // A 的事件更早
currentTime = timeA; // 当前时间取 A 的时间
valA = a[pA][1]; // 更新 A 当前状态
pA++; // 移动 A 指针
} else if (timeA > timeB) { // B 的事件更早
currentTime = timeB; // 当前时间取 B 的时间
valB = b[pB][1]; // 更新 B 当前状态
pB++; // 移动 B 指针
} else { // 两条序列同时发生事件
currentTime = timeA; // 当前时间只记录一次
valA = a[pA][1]; // 同时更新 A 的状态
valB = b[pB][1]; // 同时更新 B 的状态
pA++; // 移动 A 指针
pB++; // 移动 B 指针
}
} else if (pA < a.length) { // B 已经耗尽但 A 仍有事件
currentTime = a[pA][0]; // 获取 A 当前事件的时间
valA = a[pA][1]; // 更新 A 当前状态
pA++; // 移动 A 指针
} else { // A 已经耗尽但 B 仍有事件
currentTime = b[pB][0]; // 获取 B 当前事件的时间
valB = b[pB][1]; // 更新 B 当前状态
pB++; // 移动 B 指针
}
int combinedVal = valA + valB; // 计算当前时间点的合并值
if (combinedVal != lastEmittedVal) { // 只有合并值发生变化才输出
result.add(new int[]{currentTime, combinedVal}); // 添加新的状态变化事件
lastEmittedVal = combinedVal; // 更新最近一次输出值
}
}
return result; // 返回最终结果
}
private static List<int[]> deduplicateAndCopy(int[][] source) {
List<int[]> result = new ArrayList<>(); // 保存去重后的结果
if (source == null || source.length == 0) { // 输入为空时直接返回
return result; // 返回空列表
}
int lastValue = Integer.MIN_VALUE; // 保存最近一次输出值
for (int[] point : source) { // 遍历输入序列
int time = point[0]; // 获取事件时间
int value = point[1]; // 获取事件值
if (value != lastValue) { // 只有值发生变化才输出
result.add(new int[]{time, value}); // 添加当前事件
lastValue = value; // 更新最近一次输出值
}
}
return result; // 返回去重后的结果
}
}掌握同类考点的变体套路与最优解模板，举一反三快速拿下技术面试：