提莫攻击

难度: Easy

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的总秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

提示：

1 <= timeSeries.length <= 10⁴
0 <= timeSeries[i], duration <= 10⁷
timeSeries 按 非递减 顺序排列

Submission

运行时间: 33 ms

内存: 17.0 MB

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        total = 0  # 总时间
        pre_i, pre_j = 0, 0
        for t in timeSeries:
            i = t
            j = t + duration
            if pre_j > i:  # 需要合并
                pre_j = j
            else:  # 如果不需要合并，进行时间累计
                total += pre_j - pre_i
                pre_i = i
                pre_j = j
        total += pre_j - pre_i  # 计算最后一组区间
        return total

Explain

该题解的思路是使用区间合并的方法。遍历timeSeries数组，对于当前攻击时间t，计算出中毒的区间[i, j)，其中i=t, j=t+duration。然后判断当前区间是否与前一个中毒区间[pre_i, pre_j)重叠，如果pre_j > i，说明两个区间有重叠部分，可以将它们合并，更新pre_j为max(pre_j, j)；否则两个区间没有重叠，将前一个区间的时间累加到total，然后更新pre_i和pre_j为当前区间的起止时间。遍历结束后，将最后一个区间的时间也累加到total。最终返回total即可。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        total = 0  # 总中毒时间
        pre_i, pre_j = 0, 0  # 上一次中毒的起止时间
        for t in timeSeries:
            i = t  # 当前中毒起始时间
            j = t + duration  # 当前中毒结束时间
            if pre_j > i:  # 当前区间与上一区间重叠，需要合并
                pre_j = j  # 更新合并后的中毒结束时间
            else:  # 如果不需要合并，进行时间累计
                total += pre_j - pre_i  # 累加上一区间的中毒时间
                pre_i = i  # 更新起始时间为当前区间
                pre_j = j  # 更新结束时间为当前区间
        total += pre_j - pre_i  # 累加最后一个区间的中毒时间
        return total

Explore

区间合并方法是解决此问题的理想选择，因为它能有效处理时间序列中的重叠中毒效果。每次提莫攻击都可能在前一个攻击的中毒效果尚未结束时发生，造成中毒时间的重叠。使用区间合并方法，可以通过判断当前的攻击开始时间是否在前一个中毒时间段之内来决定是否需要合并区间，从而避免重复计算中毒时间，确保每段中毒时间只被计算一次。这样不仅提高了算法的效率，还保证了计算的准确性。

在题解中使用左闭右开的区间[i, j)表示中毒时间段主要是为了方便区间的合并和计算。在这种表示方式下，当一个中毒区间结束的时间恰好是另一个中毒区间开始的时间（即i等于前一个区间的j），这两个区间实际上是不重叠的。这样的表示方式简化了区间合并的判断逻辑，只需检查当前区间的开始时间i是否小于上一个区间的结束时间j来决定是否合并。这种表示还便于计算每个独立中毒区间的时长，直接用j - i即可得到正确的中毒时长，无需额外的处理或调整。