6.2 模拟专题：LeetCode 495. 提莫攻击

1. 题目链接

LeetCode 495. 提莫攻击

---

2. 题目描述

在《英雄联盟》中，提莫的攻击会使得敌人进入中毒状态。给定一个非递减的时间序列 timeSeries 和中毒持续时间 duration，计算敌人总的中毒时间。
规则：

• 如果两次攻击的时间间隔小于 duration，中毒时间不会叠加，而是刷新持续时间。
• 若攻击时间间隔大于等于 duration，中毒时间会完整累加。

示例：

• 输入：timeSeries = [1,4], duration = 2 → 输出：4（中毒时间区间为 [1,3) 和 [4,6)）。
• 输入：timeSeries = [1,2], duration = 2 → 输出：3（中毒时间区间为 [1,3)）。

---

3. 示例分析

1. 无重叠攻击：
   • timeSeries = [1,3,5], duration = 3 → 总时间 3 + 3 + 3 = 9。
2. 完全重叠攻击：
   • timeSeries = [1,2,3], duration = 2 → 总时间 2 + 1 + 1 = 4（最后一次攻击后持续 2 秒）。
3. 混合重叠：
   • timeSeries = [1,4,5], duration = 3 → 总时间 3 + 3 + 1 = 7。

---

4. 算法思路

核心思想：逆向遍历 + 间隔分析

1. 逆向遍历：
   • 从后向前遍历时间序列，比较相邻两次攻击的时间间隔。
2. 间隔处理：
   • 若间隔 ≥ duration：累加 duration（两次攻击的中毒时间不重叠）。
   • 若间隔 < duration：累加实际间隔时间（中毒时间被刷新）。
3. 最终累加：
   • 最后一次攻击的中毒时间固定为 duration，需单独累加。

---

5. 边界条件与注意事项

1. 空数组处理：
   • 题目保证 timeSeries 非空，无需处理。
2. 单次攻击：
   • 若 timeSeries.size() == 1，直接返回 duration。
3. 时间间隔为0：
   • 若存在重复攻击时间（如 [2,2]），视为完全重叠，仅累加 duration。
4. 大数溢出：
   • 时间值可能较大，但算法仅涉及减法运算，无需处理溢出。

---

6. 代码实现

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int n = timeSeries.size();if (n == 1) return duration; // 单次攻击直接返回int ret = 0;while (n >= 2) { // 从后向前遍历int interval = timeSeries[n-1] - timeSeries[n-2];ret += (interval >= duration) ? duration : interval;n--;}ret += duration; // 累加最后一次攻击的持续时间return ret;}
};

---

关键代码解析

1. 逆向遍历逻辑：

   while (n >= 2) {int interval = timeSeries[n-1] - timeSeries[n-2];ret += (interval >= duration) ? duration : interval;n--;
   }
   

   • 从倒数第二个元素开始，向前比较相邻时间间隔。
   • 根据间隔与 duration 的关系累加时间。

2. 最终累加：

   ret += duration;
   

   • 最后一次攻击的持续时间固定为 duration，直接累加。

---

与其他解法的对比

方法	时间复杂度	空间复杂度	核心思想
逆向遍历法	O(n)	O(1)	从后向前处理间隔，避免重复计算
正向遍历法	O(n)	O(1)	从前向后遍历，直接累加最小值
暴力模拟法	O(n + T)	O(1)	模拟每个时间点，T为总时间

---

总结

逆向遍历法通过从后向前分析时间间隔，以线性时间复杂度和常数空间复杂度高效解决问题。其核心优势在于 避免重复计算重叠时间，直接通过间隔比较确定有效中毒时间。

适用场景：

• 时间序列较长（n ≤ 1e5）。
• 需要保证代码简洁性和高效性。

关键点：

• 理解时间间隔与 duration 的关系对中毒时间的影响。
• 处理边界条件时的逻辑简化。