[LeetCode495题 - 提莫攻击] | 刷题打卡_maybelence的专栏文章_微信文章

掘金团队号上线，助你 Offer 临门！点击查看详情

前言

应该很多人都玩过 英雄联盟 这款 moba 类游戏。作为一名 coder ，在除了每天学习之外，也要有一定的娱乐时间，和朋友一起打打游戏，看看电影。适当的放松反而有助于提高学习效率。让我们刷完这题一起去召唤师峡谷驰骋吧。

题目描述

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。

你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。

示例1:

输入: [1,4], 2
输出: 4
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
第 4 秒初，提莫再次攻击艾希，使得艾希获得另外 2 秒中毒时间。
所以最终输出 4 秒。
复制代码

示例2:

输入: [1,2], 2
输出: 3
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
但是第 2 秒初，提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加，提莫在第 2 秒初的这次攻击会在第 3 秒末结束。
所以最终输出 3 。
复制代码

提示：

你可以假定时间序列数组的总长度不超过 10000。
你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数，并且不超过 10,000,000。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/im…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这一题我们可以定义一个变量 end 来维护每次中毒的时间边界,当遍历到第 i 个坐标时。如果 end 是小于或者等于 num[i] ，说明在 num[i] 秒时/之前，中毒已经结束，那么中毒的持续时长为 duration。如图，当到第 4 秒的时候，因为 end 值为 4 ，所以中间的中毒时长为 3 秒

反之，说明中毒没有结束，但是由于中毒状态的不可叠加，中毒攻击会重新生效，那中间的中毒时间就是 num[i]-num[i-1] 。当到达第 5 秒的时候，因为 end 值为 7 ，大于 5 所以中间的中毒时长为 5 - 4 = 1 。

最终代码

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int totalDuration = 0;
        int end = 0;
        for (int i = 0; i < timeSeries.length; i++) {
            if (end <= timeSeries[i]) {
                totalDuration += duration;
            } else {
                totalDuration += timeSeries[i] - timeSeries[i - 1];
            }
            end = timeSeries[i] + duration;//重新计算中毒边界
        }
        return totalDuration;
    }
}
复制代码

总结

本题只需要对 timeSeries 进行一次单次扫描即可，时间复杂度为 O(n) 。只需要注意每次 duration 与数组两个相邻元素的大小即可。因为数组长度为 0 的时候不存在中毒，且最后一次中毒的时间肯定为 duration 。上述代码的意思是默认把最后一次的中毒时间放在第 0 次计入，第 0 次加上 duration ，之后取的都是相邻元素中间的时差。

本文正在参与「掘金 2021 4 月刷题打卡」, 点击查看活动详情。喜欢的话点个赞吧。