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 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持到第 1 + 2 - 1 = 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态会维持到第 4 + 2 - 1 = 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

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

提示：

  • 1 <= timeSeries.length <= 10^4
  • 0 <= timeSeries[i], duration <= 10^7
  • timeSeries 按 非递减 顺序排列

解题思路

这道题的核心思想是模拟中毒过程。我们需要理解中毒机制：每次攻击都会让目标中毒 duration 秒，如果在中毒期间再次被攻击，中毒计时器会重置。

解题思路：

  1. 一次遍历法（推荐）：遍历攻击时间数组，对于每次攻击，计算其实际的中毒持续时间
    • 如果当前攻击时间与上次攻击的中毒结束时间有重叠，实际中毒时间为两次攻击的时间间隔
    • 如果没有重叠，实际中毒时间为完整的 duration

关键点分析：

  • 由于数组是非递减的，我们可以顺序处理每次攻击
  • 对于第 i 次攻击，如果 timeSeries[i] < timeSeries[i-1] + duration，说明中毒效果重叠了
  • 重叠情况下，实际新增的中毒时间是 timeSeries[i] - timeSeries[i-1]
  • 非重叠情况下，新增的中毒时间是完整的 duration

时间复杂度：O(n)，只需要遍历一次数组 空间复杂度：O(1)，只使用常数额外空间

这种解法简洁高效，是处理时间区间重叠问题的经典方法。

代码实现

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if (timeSeries.empty()) return 0;
        
        int totalTime = 0;
        
        for (int i = 0; i < timeSeries.size(); i++) {
            if (i == 0) {
                totalTime += duration;
            } else {
                int gap = timeSeries[i] - timeSeries[i-1];
                totalTime += min(gap, duration);
            }
        }
        
        return totalTime;
    }
};

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        if not timeSeries:
            return 0
        
        total_time = 0
        
        for i in range(len(timeSeries)):
            if i == 0:
                total_time += duration
            else:
                gap = timeSeries[i] - timeSeries[i-1]
                total_time += min(gap, duration)
        
        return total_time

public class Solution {
    public int FindPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.Length == 0) return 0;
        
        int totalTime = 0;
        
        for (int i = 0; i < timeSeries.Length; i++) {
            if (i == 0) {
                totalTime += duration;
            } else {
                int gap = timeSeries[i] - timeSeries[i-1];
                totalTime += Math.Min(gap, duration);
            }
        }
        
        return totalTime;
    }
}

/**
 * @param {number[]} timeSeries
 * @param {number} duration
 * @return {number}
 */
var findPoisonedDuration = function(timeSeries, duration) {
    if (timeSeries.length === 0) return 0;
    
    let totalTime = 0;
    
    for (let i = 0; i < timeSeries.length - 1; i++) {
        totalTime += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
    }
    
    totalTime += duration;
    
    return totalTime;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次长度为 n 的攻击时间数组
空间复杂度O(1)只使用常数个额外变量存储结果和中间计算值

相关题目