Teemo Attacking,LeetCode,495

好的，我们来详细解析一下 LeetCode 上的 495 号问题：Teemo Attacking。

题目描述

在《英雄联盟》的世界中，有一个叫 Teemo 的英雄，他的技能可以让敌人中毒。现在给定一个数组 timeSeries，其中 timeSeries[i] 表示 Teemo 在第 i 秒时对敌人发动攻击的时间点。每次攻击会让敌人中毒 duration 秒。如果 Teemo 在敌人中毒期间再次攻击，中毒时间会重新计算。

你需要计算敌人总共中毒的时间。

示例

示例 1:

输入: timeSeries = [1,4], duration = 2 输出: 4 解释: 在第 1 秒开始中毒，持续 2 秒，总共中毒 2 秒。 在第 4 秒再次攻击，重新计算中毒时间，持续 2 秒，总共中毒 4 秒。

示例 2:

输入: timeSeries = [1,2], duration = 2 输出: 3 解释: 在第 1 秒开始中毒，持续 2 秒。 在第 2 秒再次攻击，重新计算中毒时间，但只多中毒 1 秒，因为第 1 秒的攻击还在持续。

解题思路

1. 初始化变量：
   • total 用于记录总的中毒时间。
   • last 用于记录上一次攻击的时间点。
2. 遍历攻击时间点：
   • 对于每个攻击时间点 t：
     • 如果当前攻击时间点 t 与上一次攻击时间点 last 的间隔大于或等于 duration，说明上一次中毒已经结束，直接加上 duration。
     • 如果间隔小于 duration，说明上一次中毒还未结束，只加上两次攻击之间的间隔时间 t - last。
     • 更新 last 为当前攻击时间点 t。
3. 处理最后一次攻击：
   • 最后一次攻击后，无论是否有新的攻击，都需要加上 duration 秒的中毒时间。

代码实现

class Solution: def findPoisonedDuration(self, timeSeries, duration): if not timeSeries: return 0

    total = 0
    last = timeSeries[0]

    for t in timeSeries[1:]:
        if t - last >= duration:
            total += duration
        else:
            total += t - last
        last = t

    total += duration  # 处理最后一次攻击
    return total

复杂度分析

• 时间复杂度：O(n)，其中 n 是 timeSeries 的长度，因为我们只需要遍历一次数组。
• 空间复杂度：O(1)，因为我们只使用了常数级别的额外空间。

总结

这个问题的核心在于正确处理每次攻击的中毒时间，特别是当两次攻击间隔小于 duration 时，需要仔细计算实际增加的中毒时间。通过遍历攻击时间点并累加中毒时间，我们可以高效地解决这个问题。

希望这个详细的解析对你有所帮助！如果有任何进一步的问题，欢迎继续提问。