LeetCode 495. 提莫攻击：深入理解与实战解析

在《英雄联盟》这款风靡全球的游戏中，提莫以其独特的技能和机制深受玩家喜爱。而在编程的世界里，LeetCode 495. 提莫攻击问题则是一个考验我们处理时间区间重叠能力的经典题目。本文将带您一起深入理解这个问题，并提供实战解析。

问题描述

在LeetCode 495. 提莫攻击问题中，我们有一个非递减的整数数组timeSeries，其中timeSeries[i]表示提莫在timeSeries[i]秒时对艾希（寒冰射手）发起攻击。同时，我们还有一个整数duration，表示提莫的攻击使艾希进入中毒状态的时间长度。当提莫在中毒状态结束前再次发起攻击时，中毒状态会重置，并在新的攻击后持续duration秒。

我们的目标是计算艾希处于中毒状态的总秒数。

解题思路

要解决这个问题，我们需要关注两个关键点：

1. 时间区间的重叠：我们需要判断相邻两次攻击的时间区间是否有重叠，并据此计算中毒时间。
2. 中毒状态的重置：如果提莫在中毒状态结束前再次发起攻击，我们需要重置中毒计时器。

示例分析

• 示例 1：

  • 输入：timeSeries = [1, 4], duration = 2
  • 输出：4
  • 解释：提莫在第1秒和第4秒发起攻击，中毒状态分别持续2秒。由于两次攻击的时间间隔大于中毒持续时间，所以中毒时间没有重叠，总中毒时间为4秒。

• 示例 2：

  • 输入：timeSeries = [1, 2], duration = 2
  • 输出：3
  • 解释：提莫在第1秒和第2秒发起攻击，由于第二次攻击发生在第一次攻击的中毒状态持续期间，所以中毒状态被重置。两次攻击共造成3秒的中毒时间。

实战解析

为了解决这个问题，我们可以采用遍历数组的方法，依次计算每次攻击造成的中毒时间，并累加得到总中毒时间。

算法步骤

1. 初始化：设置总中毒时间totalTime为0。
2. 遍历数组：从timeSeries的第二个元素开始遍历（因为第一个元素没有前一个元素与之比较）。
3. 计算中毒时间：
   • 如果当前攻击时间与上一次攻击时间的间隔大于或等于duration，则中毒时间为duration。
   • 如果间隔小于duration，则中毒时间为当前攻击时间与上一次攻击时间的差值（因为中毒状态被重置）。
4. 累加中毒时间：将计算出的中毒时间累加到totalTime中。
5. 处理最后一次攻击：由于遍历结束时没有下一个元素与之比较，我们需要额外加上duration秒的中毒时间（如果最后一次攻击后没有新的攻击）。

示例代码（Python）

def findPoisonedDuration(timeSeries, duration):
    totalTime = 0
    n = len(timeSeries)
    for i in range(1, n):
        if timeSeries[i] - timeSeries[i-1] >= duration:
            totalTime += duration
        else:
            totalTime += timeSeries[i] - timeSeries[i-1]
    # 处理最后一次攻击
    totalTime += duration
    return totalTime
# 示例测试
print(findPoisonedDuration([1, 4], 2))  # 输出: 4
print(findPoisonedDuration([1, 2], 2))  # 输出: 3

总结

通过本文的解析，我们深入理解了LeetCode 495. 提莫攻击问题的本质，并掌握了处理时间区间重叠问题的方法。在实际应用中，这类问题常常出现在需要处理时间序列数据的场景中，如日志分析、事件追踪等。希望本文能为您解决类似问题提供有益的参考。