第一次在题单里看到“提莫攻击”这四个字时我愣了一下以为点进了游戏资讯。看清题目以后才发现名字再花哨考的还是非常经典的模拟功底某个英雄按固定攻击时刻发起攻击每次命中会让目标陷入持续若干秒的中毒状态如果中毒还没结束又被命中就把中毒结束时刻往后刷新。最后要算的是目标在整个过程中一共有多少秒处于中毒状态。这道题很适合用来练“模拟”这一算法思想。你别看它描述像游戏技能剥掉外壳以后就是一个时间轴上的区间合并问题而且因为攻击时间默认有序解法可以压到一次遍历完成时间复杂度 O(n)空间复杂度 O(1)。这篇文章我会用 C 从题意建模、公式推导、代码实现、边界测试一直讲到如何把这类“状态重置”的模型扩展到其他题目和真实业务场景希望看完全文的人能完全吃透它而不是背个答案就完事。1. 题目到底在描述什么1.1 先明确输入和输出题目会给两个信息一个是攻击时刻数组timeSeries一个是中毒持续时间duration。数组里的每个数字timeSeries[i]表示第 i 次攻击发生的时刻题目默认从小到大排列。每次攻击都会让目标从timeSeries[i]这一时刻开始中毒持续duration秒。如果目标在中毒期间又被打中旧的剩余中毒时间直接作废重新从新攻击时刻计算满额的duration秒。要求输出目标最终处于中毒状态的总秒数。有人会问如果两次攻击之间隔了很久中毒状态已经消失那新攻击是不是重新开始一个段是的这就是“重置”的核心语义。所以问题最后不是把所有攻击各自贡献的时间简单相加而是要处理区间之间产生的重叠。1.2 亲手推两个小例子先看最简单的情况timeSeries [1, 2]duration 2。第一次攻击在时刻 1 发生目标从第 1 秒开始中毒持续 2 秒也就是直到第 3 秒结束。第二次攻击发生在时刻 2此时目标还处于第一次的中毒状态中所以剩余时间作废重新从第 2 秒开始中毒 2 秒最终到第 4 秒结束。两次攻击带来的中毒区间分别是 [1, 3) 和 [2, 4)合并以后的覆盖范围是 [1, 4)一共 3 秒。再看timeSeries [1, 4]duration 2。第一次攻击让目标在 [1, 3) 中毒第二次攻击发生在时刻 4这时上一次中毒已经结束所以第二次重新开启一段 [4, 6)。两个区间完全不重叠答案是 3 3 6 秒。注意这里的端点写法我用的是左闭右开区间含义是“开始时刻算中毒结束时刻已经恢复”后面解析边界时还会再讨论。1.3 把问题抽象成区间求并集做过区间类题目的同学应该已经察觉这道题的底层模型和“合并区间”非常像。每一次攻击都可以看作一个区间[t_i, t_i duration)如果区间之间有重叠会被后面的攻击“重置”并往后延伸最终答案就是所有这些区间合并后的总长度。不妨把“中毒状态”想象成一条时间线上的连续段。当新的攻击到来时只有两种情况新攻击时刻落在当前中毒段内那么当前段的右边界向右扩展。新攻击时刻落在当前中毒段之外那么产生一个全新中毒段。这个认知是整个模拟策略的基础。接下来所有代码和公式都是在处理这个“当前中毒段”如何被更新。2. 解法核心比较相邻攻击时间差2.1 千万不要真的逐秒模拟最直接的模拟思路是准备一个布尔数组把中毒的每一秒都标记成 true最后数 true 的个数。数组规模小的时候没问题可一旦攻击时间跨度大比如最后一秒是 10 的 9 次方级别这种逐秒模拟就会立刻超时空间也完全扛不住。正确的思路是不去枚举每一个时间点而去模拟中毒区间的“变化过程”。对一个真正在时间轴上游走的连续区间来说我们只需要关心区间什么时候开始、什么时候结束不需要关心中间每一秒到底发生了什么。这个区别值得强调一下。很多新手以为模拟题就必须循环到每个时刻其实“模拟”这个词的重点是“用程序忠实还原状态变化”不是“无脑完整遍历底层细节”。一个策略如果能在状态发生跳变的关键节点上准确还原变化那它就是合格的模拟而且会高效得多。2.2 任意相邻两次攻击的贡献公式设当前处理的攻击时刻为timeSeries[i]前一次攻击时刻为timeSeries[i-1]。因为整个数组按时间递增所以两次攻击之间的时间差是diff timeSeries[i] - timeSeries[i-1]这个diff决定了两件事上一次中毒是否已经结束以及这一次攻击能给总中毒时间新增多少秒。如果diff duration说明上一次攻击造成的中毒在本次攻击发生之前已经完全结束。那么本次攻击会开启一段全新的中毒区间给答案总额增加满额的duration秒。如果diff duration说明本次攻击发生时目标还在上一次攻击造成的中毒状态中。上一次攻击已经把区间开到了timeSeries[i-1] duration本次攻击从更晚的时刻timeSeries[i]开始重新计时只是把中毒结束时刻从timeSeries[i-1] duration推到了timeSeries[i] duration。对于总答案来说新增的部分并不是duration而是两个攻击时刻之间的间隔diff。两种情况下累计新增都可以统一写成新增量 min(duration, timeSeries[i] - timeSeries[i-1])第一次攻击没有前一攻击它一定会开一个满额的中毒区间所以单独加上duration即可。2.3 用时间线验证一下公式拿一个稍微复杂点的例子验证timeSeries [1, 2, 6]duration 4。攻击时刻 1前面没有数据新增 4累计 4。区间是 [1, 5)。攻击时刻 2与上次差 1小于 4新增 1累计 5。区间 [1, 5) 被刷新成 [2, 6)但整体覆盖仍是从 1 到 6所以只多了中间这 1 秒。攻击时刻 6与上次差 4等于 duration上一次中毒刚好结束新增 4累计 9。区间 [2, 6) 结束新开 [6, 10)。最终答案是 9。手动画一下时间线也知道[1, 6) 有 5 秒[6, 10) 有 4 秒合计正好 9 秒。这个例子非常有代表性因为它出现了“相邻差正好等于 duration”的情况。此时两次中毒之间没有任何重叠新攻击会作为新段的起点所以贡献满额 duration。3. C 的两种主流写法与取舍3.1 写法一直接用相邻攻击差叠加先处理空数组再把第一段 duration 加进去之后从下标 1 开始遍历class Solution { public: int findPoisonedDuration(vectorint timeSeries, int duration) { int n timeSeries.size(); if (n 0) return 0; int total duration; for (int i 1; i n; i) { total min(duration, timeSeries[i] - timeSeries[i - 1]); } return total; } };这段代码很短但信息量很足。total duration是在处理第一次攻击。min(duration, timeSeries[i] - timeSeries[i - 1])是核心公式。timeSeries[i] - timeSeries[i - 1]不需要担心负数因为题目保证了数组升序。这种写法的好处是简单直观面试时容易讲清楚“我维护的是每个新攻击带来的增量”坏处是代码里看不到“当前中毒段”的实体理解不透彻的话容易在讨论为什么是diff而不是duration时卡壳。3.2 写法二显式维护中毒窗口边界如果你更喜欢“模拟状态本身”的感觉可以维护一个当前中毒窗口的起点start和终点end。class Solution { public: int findPoisonedDuration(vectorint timeSeries, int duration) { int n timeSeries.size(); if (n 0) return 0; int total 0; int start timeSeries[0]; int end timeSeries[0] duration; for (int i 1; i n; i) { if (timeSeries[i] end) { // 上一次中毒已结束先结算上一个窗口 total end - start; // 开启新窗口 start timeSeries[i]; end timeSeries[i] duration; } else { // 上一次中毒还在把窗口右边界刷新 end timeSeries[i] duration; } } total end - start; return total; } };这段代码里的start和end就是“当前正在延续的中毒窗口”。每次攻击到来时如果攻击时刻已经大于等于窗口结束时刻end说明上一个窗口彻底结束先把它的长度end - start结算进答案然后开启新窗口。如果攻击时刻还在窗口内说明需要重置剩余时间直接把end改成timeSeries[i] duration。最后循环结束后还要再结算一次把最后一个窗口的长度加上去。这种写法更像在“模拟”一个状态变量。代码比写一多几行但可读性更强尤其适合给面试官讲“中毒过程中发生攻击时我做了哪些状态变更”。3.3 两种写法怎么互相验证我建议把两种写法都掌握因为它们是同一套逻辑的两种观察角度。写法一看的是“每个新攻击给答案新增多少”。写法二看的是“每个连续中毒窗口整体长度是多少”。对应关系是当相邻攻击差小于 duration 时窗口方法会进入 else 分支把end往后推写法一的min函数会累加 diff。当相邻攻击差大于等于 duration 时窗口方法会进入 if 分支结算旧窗口并开启新窗口写法一的min函数会累加满额 duration。两种写法在复杂度和最终结果上完全一致。如果你在写完代码以后担心边界有问题可以用写法二去验证写法一或者反过来。刷题时多准备一条互相印证的思路比单独记代码要可靠得多。3.4 复杂度与前提条件两种写法的复杂度都一样时间复杂度 O(n)因为只需要扫一遍攻击时刻数组。空间复杂度 O(1)只用了几个整数变量。如果数组没有排序需要先排序复杂度变成 O(n log n)。这道题通常会明确说明数组按时间递增面试时如果没说最好和面试官确认一下或者自己主动加一次排序保证不出错。另外如果题目给出的时间戳范围特别大或者累计时长可能超过 32 位整数可以在代码里把int total换成long long total。大部分情况下题目默认答案在 int 范围内但养成用更宽类型接收累计结果的习惯不是坏事。4. 写代码时最容易翻车的几个位置4.1 空数组和单元素数组空数组是第一个必须处理的边界。很多人在写法一中直接从timeSeries[1]开始遍历没先检查timeSeries.empty()程序直接访问非法下标崩溃。单元素数组相对温和total duration之后直接返回答案即可写法二也能因循环不执行而正确输出 duration。我把边界处理放在代码靠前位置是因为这类防御性操作越早判断越不容易漏。面试时写if (n 0) return 0;属于基础素养不会加分但漏掉一定会减分。4.2 duration 比整个时间跨度还大举个极端例子timeSeries [0, 1, 2]duration 100。很多人下意识会觉得每次攻击都能贡献 100 秒于是写出 300。但实际答案不是 300因为第二次攻击和第三次攻击发生时中毒状态都没有结束只是把结束时间不断往后推进。第一次攻击区间 [0, 100]贡献 100。第二次攻击在时刻 1把区间刷新成 [1, 101]整体覆盖 [0, 101]相比之前只多了第 100 秒这 1 秒。第三次攻击在时刻 2把区间刷新成 [2, 102]整体覆盖 [0, 102]又只多了 1 秒。最终答案是 102。用公式写出来是total 100 min(100, 1) min(100, 1) 102这个例子很好地说明了一个原则杀掉一次攻击重置的是“剩余时长”和“结束时刻”但不代表每一次攻击都能让答案增加满额 duration。真正能把贡献拉满的前提是两次攻击之间至少隔了完整 duration 的时间。4.3 “秒”到到底怎么算这是初学者最容易打架的地方。题目说中毒持续 2 秒那攻击发生在第 1 秒中毒范围到底是第 1、2 秒还是第 1 秒结束就算毒完我建议统一用左闭右开区间来理解攻击发生在 t中毒持续时间 duration 中毒区间就是 [t, t duration)在这个区间中时刻 t 是中毒状态时刻 t duration 已经不再中毒。持续 2 秒的意思是时刻 1 和时刻 2 算中毒时刻 3 开始恢复。如果下次攻击刚好发生在时刻 3那么两次中毒不重叠各自贡献满额 duration。回到代码timeSeries[i] end判断为真时结算旧窗口并开新窗口正是采用了这个语义。哪怕攻击时刻等于旧的结束时刻也认为上一次中毒已经结束因为右端点是开区间。4.4 数组没有排序怎么办虽然原题通常保证升序但本着严谨的思路还是提一下如果你拿到的数据没有排序必须先排序再使用相邻差公式。因为公式里默认timeSeries[i]是当前最新攻击只有按时间顺序处理窗口边界才是连续的。排序只需要一行sort(timeSeries.begin(), timeSeries.end());排序以后再去跑上面的代码整体复杂度变成 O(n log n)。面试中如果面试官故意换了一个乱序数组你不仅能发现还能顺手解决这会成为明显的加分项。4.5 如果攻击时刻相同呢有些扩展版本可能存在同一时刻连续攻击的情况。此时两次攻击时间差为 0公式会得到新贡献 0因为第二次攻击发生时还处于第一次中毒状态结束时间也没变化。若重叠区域处理不当代码很可能会重复计算一次 duration所以遇到重复时间戳时要保持警惕。幸运的是原题的递增序列一般不会出现重复但你自己扩展练习时可以考虑这个变体。5. 把“模拟中毒窗口”扩展到更多场景5.1 思路一整道题退化为区间合并如果不要求一次遍历其实这道题还有更通用的做法把每次攻击都构造成区间[timeSeries[i], timeSeries[i] duration)然后执行一次区间合并最后把合并后的区间长度加起来。区间合并模板是算法面试常客基本逻辑是把所有区间按起点排序。用一个当前区间[curStart, curEnd)依次扫描。如果新区间起点在当前区间终点之前说明有重叠更新当前区间终点为两者较大值。否则结算当前区间再开启新区间。这样做的复杂度和题目给出数组的有序性有关但思想更通用适合对“区间求并集”这种抽象模型不熟的同学作为切入点。如果已经把这道题的题意理解成了合并区间后面再遇到一堆类似题目都会容易很多。5.2 思路二改成通用的事件窗口模板把“提莫攻击”这个外壳拿掉核心就是一个很通用的事件处理模型每个事件发生在一个时刻会启动一个持续 window 的状态。 如果事件发生时上一个状态窗口没过期就把窗口结束时刻刷新到当前事件时刻 window。 如果事件发生时上一个状态窗口已经过期那就先结算旧窗口再开启新窗口。这套模板可以套到很多地方。比如服务器收到一次请求给某个资源设置一个 window 秒的缓存缓存没过期又来了新请求就用新请求刷新缓存过期时间。网络重试场景中某个错误状态进入后持续若干秒期间又出现新错误则需要把恢复时间往后推。游戏里的各种“持续伤害刷新”机制本质都是这个模型。所以代码里那几行 if、else 看起来很朴素背后代表的是一种“基于状态截止时刻”的建模方式。你掌握了以后遇到任何“过期时间刷新”类问题都可以直接迁移。5.3 思路三何时升级到差分数组或扫描线如果题目只是要求总中毒秒数窗口模拟是最优解。但地图大了以后问题可能会变成每个区间长度不同还要求某个时间段内同时处于几个状态。攻击次数不多但时间轴非常稀疏且要多次查询。需要知道目标有多少秒处于“至少两层中毒”的状态。这时候就要考虑差分数组或者扫描线事件在每个攻击开始时刻记录一个加一事件。在每个中毒结束时刻记录一个减一事件。扫描时间轴维护当前重叠区间数量再按需求统计。这种做法的好处是能统计覆盖次数不只是覆盖长度但代价是需要额外排序事件空间也可能更大。所以选型时要先想清楚题目问的是“总长度”还是“覆盖次数”问总长度优先用窗口模拟问覆盖次数再升级到扫描线。我给个简单的伪代码作为扩展记录vectorpairint, int events; for (int t : timeSeries) { events.push_back({t, 1}); events.push_back({t duration, -1}); } sort(events.begin(), events.end()); int current 0; long long total 0; for (int i 0; i events.size(); i) { int now events[i].first; int delta events[i].second; if (current 0 i 0) { total now - events[i - 1].first; } current delta; }这段伪代码能算出所有中毒覆盖的总长度而且它能告诉你什么时候中毒层数从 1 变成 2、从 2 变成 1。如果面试官打算把难度往上调这类扩展是常见升级路径。不过你要是第一时间能给出那道题的 O(n) 窗口模拟通常已经达到了目标。这道题看起来短其实把“区间重置”“相邻贡献”“边界语义”几个点都揉在了一起。我自己每次写它都会刻意在脑子里画一遍时间轴先确认两次攻击是否重叠再决定贡献是 duration 还是 diff。写完之后再用窗口写法交叉验证一遍基本不会出错。最后分享一个小习惯刷模拟题不要把代码写得过于“灵性”哪怕是一行min(duration, timeSeries[i] - timeSeries[i-1])也要能边说边解释为什么是它。真正让模拟题拉开差距的往往不是你能不能写出代码而是你能不能把那个“状态刷新”的过程讲得让听的人也瞬间明白。