0495. Teemo Attacking¶
题目信息¶
- 题号:
0495
- 难度:
Easy
- 主题:
攻击时间、中毒区间、持续时间刷新、总时长
- 原题:
- 重点:
每次攻击从该秒开始持续
duration秒、重叠时间不能重复计数、新攻击会延长或刷新中毒结束时间
题目重述¶
数组 timeSeries 按严格递增顺序记录提莫发动攻击的时间。每次攻击会让目标从当前时刻开始中毒 duration 秒,也就是覆盖离散时间区间 [t, t + duration - 1]。
若下一次攻击发生时目标仍在中毒,新效果与原效果重叠,重叠秒数只能计入一次,同时中毒结束时间按新攻击重新延后。返回目标处于中毒状态的总秒数。
timeSeries.length 位于 [1, 10^4],攻击时间位于 [0, 10^7],duration 位于 [1, 10^7]。结果等于所有中毒时间区间并集的长度。
自建示例¶
前两次攻击重叠,最后一次分离:
输入:timeSeries = [1,3,10],duration = 4
输出:10
解释:前三个中毒区间为 [1,4]、[3,6]、[10,13];前两个合并为 1..6 共 6 秒,最后一个贡献 4 秒,总计 10 秒。
每次攻击恰好无重叠:
输入:timeSeries = [0,2,4],duration = 2
输出:6
解释:区间分别为 [0,1]、[2,3]、[4,5],相邻但不重叠,总长度为 6。
相邻攻击的新增贡献取间隔与持续时间的较小值¶
第一击一定贡献 duration 秒。对于相邻攻击时间差 gap:若 gap >= duration,前一次中毒已经结束,新攻击再贡献完整的 duration;若 gap < duration,前一次效果只覆盖到下一击前,新增贡献只有 gap 秒。因此每次新增长度是 min(duration, gap)。
按题意区间是离散的 [t, t + duration - 1],所以相差 duration 时恰好不重叠,不能写成小于等于的重叠判断。
C++ 实现¶
class Solution {
public:
int findPoisonedDuration(std::vector<int>& timeSeries,
int duration) {
long long total = duration;
for (int i = 1; i < static_cast<int>(timeSeries.size()); ++i) {
long long gap = static_cast<long long>(timeSeries[i]) -
timeSeries[i - 1];
total += std::min<long long>(duration, gap);
}
return static_cast<int>(total);
}
};
代码分析¶
只保留相邻攻击的时间差即可计算区间并集长度;时间序列已经严格递增,不需要排序或维护全部区间。遍历一次得到 O(n) 时间和 O(1) 额外空间,累计值用 long long 防止中间加法溢出。