LeetCode-Go 题解 495：Teemo Attacking（提莫攻击）——中毒区间的合并累计与贪心扫描
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
LeetCode 495 题 "Teemo Attacking"（提莫攻击）是一道经典的数组区间合并类问题：给定一组非递减的攻击时间戳与固定的中毒持续时间，求敌方英雄处于中毒状态的总秒数。本篇文章以 leetcode/0495.Teemo-Attacking/README.md 的官方题解为骨架，结合 LeetCode-Go 仓库中的 Go 实现源码 与单元测试，完整讲解题目语义、区间重叠判断的关键边界、单次线性扫描的贪心解法及其复杂度证明，并给出可直接运行验证的代码与测试命令。读完本文，你将掌握"区间合并 + 相邻差量累计"这类时间轴问题的通用思考方式，并能独立写出 O(n) 时间、O(1) 空间的解决方案。
一、题目背景与完整描述
本题的背景取自 MOBA 游戏《英雄联盟》：英雄"提莫"（Teemo）攻击敌方"艾希"（Ashe，寒冰射手）后，艾希会进入持续duration秒的中毒状态。
题目原文描述如下：
Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for exactly
durationseconds.More formally, an attack at second
twill mean Ashe is poisoned during the inclusive time interval[t, t + duration - 1].If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will end
durationseconds after the new attack.You are given a non-decreasing integer array
timeSeries, wheretimeSeries[i]denotes that Teemo attacks Ashe at secondtimeSeries[i], and an integerduration.Return the total number of seconds that Ashe is poisoned.
用中文概括题意为：
- 提莫在
t秒发起攻击，意味着艾希在闭区间[t, t + duration - 1]（含两端）内处于中毒状态； - 如果提莫在本次中毒效果结束之前再次攻击，中毒计时器会被重置，新的攻击之后中毒状态将再持续
duration秒； - 输入是一个非递减的整数数组
timeSeries（timeSeries[i]表示第i次攻击发生在第timeSeries[i]秒）和一个整数duration； - 要求返回艾希处于中毒状态的总秒数。
二、示例推演：理解"重置"语义
原题解给出了两个极具代表性的示例，先完整过一遍：
示例 1：timeSeries = [1,4], duration = 2，输出4
- 第 1 秒，提莫攻击，艾希在第 1、2 秒中毒； - 第 4 秒，提莫攻击，艾希在第 4、5 秒中毒。 艾希在第 1、2、4、5 秒处于中毒状态，总计 4 秒。两次攻击（第 1 秒与第 4 秒）之间间隔 3 秒，大于duration - 1 = 1，上一次中毒（第 2 秒）结束后下一次攻击（第 4 秒）才开始，两个中毒区间完全不重叠，因此总时长直接相加：2 + 2 = 4。
示例 2：timeSeries = [1,2], duration = 2，输出3
- 第 1 秒，提莫攻击，艾希在第 1、2 秒中毒； - 第 2 秒，提莫再次攻击并重置中毒计时器，艾希在第 2、3 秒中毒。 艾希在第 1、2、3 秒处于中毒状态，总计 3 秒。第 1 秒的攻击使艾希中毒到第 2 秒，而第 2 秒的攻击发生在中毒尚未结束时，计时器被重置，中毒延续到第 3 秒。两个中毒区间[1, 2]与[2, 3]首尾相接、发生重叠，合并后为[1, 3]，共 3 秒，而不是简单的2 + 2 = 4。这正是本题与"朴素累加"的差异所在：重叠部分不能重复计数。
三、约束条件与边界意识
原题给定的约束如下：
1 <= timeSeries.length <= 100000 <= timeSeries[i], duration <= 10000000timeSeries按非递减顺序排列
从约束可以提炼出三个对实现有直接影响的点：
- 数组长度最大 10000：O(n) 的线性扫描完全够用，任何 O(n²) 的双重循环都不必要；
duration可以为 0：当duration = 0时每次攻击不产生任何中毒时间，代码必须能正确处理返回 0；- 攻击时间戳允许重复（非递减而非严格递增）：
timeSeries[i] == timeSeries[i-1]是合法输入，此时属于完全重叠，区间合并逻辑必须覆盖这种情况。
四、核心思路：把问题抽象成"区间合并 + 相邻差量累计"
4.1 问题本质是一维闭区间合并
每次攻击产生一个长度为duration的闭区间[t, t + duration - 1]。题目要求的"中毒总秒数"，本质就是这些区间并集的长度。由于攻击时间戳按非递减排列，区间在时间轴上天然有序，因此可以用单次扫描完成合并计数，不需要排序，也不需要记录所有区间。
4.2 相邻两次攻击只有两种关系
设当前正在考察的是第i-1次攻击（时间t = timeSeries[i-1]）与第i次攻击（时间timeSeries[i]），并记end = t + duration - 1为第i-1次攻击造成的中毒结束时刻。两种情形为：
- 区间断开（
end < timeSeries[i]）：上一次中毒在下次攻击之前就已结束，两次中毒完全独立。前一次攻击应完整计入duration秒； - 区间重叠（
end >= timeSeries[i]）：下次攻击发生时中毒仍在持续，计时器重置。此时从第i-1次攻击到第i次攻击之间，新增的中毒时间是timeSeries[i] - t秒（从t秒到timeSeries[i]秒前一刻），而timeSeries[i]这一秒起的中毒时间将交给"最后一次攻击的完整duration"统一兜底。
4.3 关键边界：为什么必须是严格小于end < timeSeries[i]
注意中毒区间是闭区间[t, t + duration - 1]。当end == timeSeries[i]时，即下一次攻击恰好发生在上一次中毒的最后一秒：
- 例如
timeSeries = [1, 2], duration = 2：第 1 秒攻击中毒区间[1, 2]，第 2 秒攻击触发重置； - 合并后总时长为
timeSeries[i] - t + duration = 2 - 1 + 2 = 3秒，与示例 2 的输出完全一致。
因此在判断时必须使用end < timeSeries[i]（严格小于）判定为"断开"，而end >= timeSeries[i]（含相等）一律按"重叠"处理。若误写成end <= timeSeries[i]，示例 2 会被错误地算成2 + 2 = 4秒。
五、Go 实现：来自仓库的完整解法
原题解给出的核心解法如下，源码位于 495.Teemo Attacking.go：
package leetcode func findPoisonedDuration(timeSeries []int, duration int) int { var ans int for i := 1; i < len(timeSeries); i++ { t := timeSeries[i-1] end := t + duration - 1 if end < timeSeries[i] { ans += duration } else { ans += timeSeries[i] - t } } ans += duration return ans }逐段解读算法流程：
- 循环从
i = 1开始，每次考察相邻的两次攻击timeSeries[i-1]与timeSeries[i]； - 记
t = timeSeries[i-1]，end = t + duration - 1为上一次攻击的中毒结束时刻（闭区间右端点）； - 若
end < timeSeries[i]（区间断开）：上一次攻击完整贡献duration秒，ans += duration； - 否则（区间重叠，含首尾相接）：只累计到下一次攻击前的新增部分
timeSeries[i] - t秒； - 循环结束后，最后一次攻击必定产生一个完整的
duration秒中毒区间，因此最后统一ans += duration并返回。
用示例 2 走一遍：timeSeries = [1,2], duration = 2。
i = 1：t = 1，end = 1 + 2 - 1 = 2，end >= timeSeries[1] = 2，走重叠分支，ans += 2 - 1 = 1；- 循环结束，
ans += duration = 2，总ans = 3，输出正确。
六、等价写法与复杂度分析
6.1 更紧凑的等价写法
上面的分支判断可以用min函数等价压缩：区间断开时duration <= timeSeries[i] - t，重叠时duration > timeSeries[i] - t，因此每次累计的新增时长恰好是两者的较小值：
func findPoisonedDuration(timeSeries []int, duration int) int { ans := 0 for i := 1; i < len(timeSeries); i++ { ans += min(duration, timeSeries[i]-timeSeries[i-1]) } return ans + duration }两种写法在数学上完全等价，区别只是风格。仓库当前的 go.mod 声明go 1.19，在该版本下min尚不是内建函数，因此原题解使用显式的if/else分支，避免引入额外依赖，这一点也体现了实现上的版本兼容考量。
6.2 复杂度
- 时间复杂度 O(n)：单次线性扫描，
n为timeSeries的长度，与时间戳的绝对数值大小无关； - 空间复杂度 O(1)：只使用常数个变量，不依赖额外存储。
即便输入规模达到约束上限（长度 10000、时间戳 10^7），也能在微秒量级内完成计算，不存在溢出风险（t + duration最大约 2×10^7，远小于int上限）。
七、测试验证：仓库测试用例与运行方式
7.1 仓库内建的两个用例
仓库在 495.Teemo Attacking_test.go 中为本题提供了与题解示例一一对应的测试用例：
输入timeSeries | 输入duration | 期望输出 |
|---|---|---|
[1, 4] | 2 | 4 |
[1, 2] | 2 | 3 |
测试代码通过Test_Problem495遍历用例表并打印输入输出，覆盖了"区间断开"与"区间重叠（首尾相接）"两条核心路径。你可以补充更多边界用例自行验证，例如：
timeSeries = [1], duration = 5→ 单次攻击，输出5（对应循环体一次都不执行、最后ans += duration的分支）；timeSeries = [1, 1], duration = 2→ 攻击时间戳重复，区间完全重叠，输出2；timeSeries = [1, 2, 3], duration = 2→ 连续攻击不断重置计时器，输出4（合并区间[1, 4]）。
7.2 如何运行测试
仓库根目录的 gotest.sh 定义了全量测试方式，其核心命令是对所有题解包做覆盖率测试：
go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...单独验证本题时，可以只运行本题目录下的测试：
go test -v ./leetcode/0495.Teemo-Attacking/仓库在根目录维护了 coverage.txt 覆盖率文件，并在项目描述中宣称 100% 测试覆盖，测试基建（含覆盖率收集脚本）由 gotest.sh 统一支撑，因此本题实现同样受到该机制的约束与验证。
八、总结
LeetCode 495（Teemo Attacking）的核心价值在于把一个"带重置语义的时间轴计数"问题，转化为有序闭区间的并集长度计算：
- 攻击序列非递减保证了相邻区间有序，使单次扫描成为可能；
- 判断重叠时务必注意闭区间特性，用
end < timeSeries[i]严格小于判定断开，end >= timeSeries[i]（含端点重合）判定重叠； - 每次迭代只累计"相邻两次攻击之间的新增时长"，最后一次攻击的完整
duration在循环外统一追加，从而规避重复计数； - 整体解法为 O(n) 时间、O(1) 空间，与 LeetCode-Go 仓库其他题解的风格一致，并配有可直接运行的 单元测试 佐证正确性。
掌握这一"相邻差量累计 + 收尾兜底"的模式后，遇到形如区间合并、覆盖时长统计、时间轴去重等一类问题，都可以快速套用同样的思维框架。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
