LeetCode-Go 题解 495Teemo 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 exactlydurationseconds.More formally, an attack at secondtwill 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 enddurationseconds after the new attack.You are given a non-decreasing integer arraytimeSeries, 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秒输入是一个非递减的整数数组timeSeriestimeSeries[i]表示第i次攻击发生在第timeSeries[i]秒和一个整数duration要求返回艾希处于中毒状态的总秒数。二、示例推演理解重置语义原题解给出了两个极具代表性的示例先完整过一遍示例 1timeSeries [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。示例 2timeSeries [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按非递减顺序排列从约束可以提炼出三个对实现有直接影响的点数组长度最大 10000O(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.gopackage 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 1t 1end 1 2 - 1 2end 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]24[1, 2]23测试代码通过Test_Problem495遍历用例表并打印输入输出覆盖了区间断开与区间重叠首尾相接两条核心路径。你可以补充更多边界用例自行验证例如timeSeries [1], duration 5→ 单次攻击输出5对应循环体一次都不执行、最后ans duration的分支timeSeries [1, 1], duration 2→ 攻击时间戳重复区间完全重叠输出2timeSeries [1, 2, 3], duration 2→ 连续攻击不断重置计时器输出4合并区间[1, 4]。7.2 如何运行测试仓库根目录的 gotest.sh 定义了全量测试方式其核心命令是对所有题解包做覆盖率测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...单独验证本题时可以只运行本题目录下的测试go test -v ./leetcode/0495.Teemo-Attacking/仓库在根目录维护了 coverage.txt 覆盖率文件并在项目描述中宣称 100% 测试覆盖测试基建含覆盖率收集脚本由 gotest.sh 统一支撑因此本题实现同样受到该机制的约束与验证。八、总结LeetCode 495Teemo 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），仅供参考 LeetCode-Go 题解 495：Teemo Attacking（提莫攻击）——中毒区间的合并累计与贪心扫描
LeetCode-Go 题解 495Teemo 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 exactlydurationseconds.More formally, an attack at secondtwill 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 enddurationseconds after the new attack.You are given a non-decreasing integer arraytimeSeries, 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秒输入是一个非递减的整数数组timeSeriestimeSeries[i]表示第i次攻击发生在第timeSeries[i]秒和一个整数duration要求返回艾希处于中毒状态的总秒数。二、示例推演理解重置语义原题解给出了两个极具代表性的示例先完整过一遍示例 1timeSeries [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。示例 2timeSeries [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按非递减顺序排列从约束可以提炼出三个对实现有直接影响的点数组长度最大 10000O(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.gopackage 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 1t 1end 1 2 - 1 2end 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]24[1, 2]23测试代码通过Test_Problem495遍历用例表并打印输入输出覆盖了区间断开与区间重叠首尾相接两条核心路径。你可以补充更多边界用例自行验证例如timeSeries [1], duration 5→ 单次攻击输出5对应循环体一次都不执行、最后ans duration的分支timeSeries [1, 1], duration 2→ 攻击时间戳重复区间完全重叠输出2timeSeries [1, 2, 3], duration 2→ 连续攻击不断重置计时器输出4合并区间[1, 4]。7.2 如何运行测试仓库根目录的 gotest.sh 定义了全量测试方式其核心命令是对所有题解包做覆盖率测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...单独验证本题时可以只运行本题目录下的测试go test -v ./leetcode/0495.Teemo-Attacking/仓库在根目录维护了 coverage.txt 覆盖率文件并在项目描述中宣称 100% 测试覆盖测试基建含覆盖率收集脚本由 gotest.sh 统一支撑因此本题实现同样受到该机制的约束与验证。八、总结LeetCode 495Teemo 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），仅供参考