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