TNotes.leetcode

Appearance

0495. 提莫攻击【简单】

0495. 提莫攻击【简单】 ​

1. 📝 题目描述 ​

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number[]} timeSeries
 * @param {number} duration
 * @return {number}
 */
var findPoisonedDuration = function (timeSeries, duration) {
  if (timeSeries.length === 0 || duration === 0) {
    return 0
  }

  let totalDuration = 0

  // 遍历攻击时间序列，计算每次攻击对中毒时间的贡献
  for (let i = 0; i < timeSeries.length - 1; i++) {
    // 计算相邻两次攻击的时间间隔
    const gap = timeSeries[i + 1] - timeSeries[i]

    // 如果间隔小于中毒持续时间，则只能贡献gap秒中毒时间
    // 否则可以贡献完整的duration秒中毒时间
    totalDuration += Math.min(gap, duration)
  }

  // 最后一次攻击总是能贡献完整的duration秒中毒时间
  totalDuration += duration

  return totalDuration
}

3. 🎯 s.2 - 使用 Set 记录所有中毒时间点 ​

js
/**
 * @param {number[]} timeSeries
 * @param {number} duration
 * @return {number}
 */
var findPoisonedDuration = function (timeSeries, duration) {
  if (timeSeries.length === 0 || duration === 0) {
    return 0
  }

  // 使用 Set 记录所有中毒的时间点
  const poisonedTimes = new Set()

  // 遍历每次攻击
  for (const attackTime of timeSeries) {
    // 将这次攻击导致的中毒时间点加入 Set
    for (let i = 0; i < duration; i++) {
      poisonedTimes.add(attackTime + i)
    }
  }

  return poisonedTimes.size
}
  • 超时

4. 🎯 s.3 - 区间合并法 ​

js
/**
 * @param {number[]} timeSeries
 * @param {number} duration
 * @return {number}
 */
var findPoisonedDuration = function (timeSeries, duration) {
  if (timeSeries.length === 0 || duration === 0) {
    return 0
  }

  const intervals = [] // 存储所有中毒区间，不考虑是否重叠。
  for (const attackTime of timeSeries) {
    intervals.push([attackTime, attackTime + duration - 1])
  }

  const merged = [intervals[0]] // 存储所有去除重叠区间后的中毒区间。

  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1]
    const current = intervals[i]

    // 如果当前区间与上一个区间重叠，则合并
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1])
    } else {
      // 否则添加新区间
      merged.push(current)
    }
  }

  // 计算总中毒时间
  let total = 0
  for (const [start, end] of merged) {
    total += end - start + 1
  }

  return total
}
  • 相较于解法 1，这种解法能获取到中毒的时间区间。

Discussions