LeetCode刷题题解：495. 提莫攻击

buildupchao 发布于2021-11-11 16:55 / 3452人阅读

摘要：正式地讲，提莫在发起发起攻击意味着艾希在时间区间含和处于中毒状态。示例输入输出解释提莫攻击对艾希的影响如下第秒，提莫攻击艾希并使其立即中毒。第秒，提莫再次攻击艾希，艾希中毒状态又持续秒，即第秒和第秒。

495. 提莫攻击

题目：

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

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

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

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

示例1：

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

示例2：

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

解题思路：

这道题为简单题，只需遍历数组计算相邻元素间的差值和持续时间的最小值，然后累加求和，也就是统计除了最后一个中毒持续时间的前面的中毒持续时间和，因为最后的中毒持续时间是一定的，所以将求和结果加上duration返回即可。

代码：

class Solution {    public int findPoisonedDuration(int[] timeSeries, int duration) {    	int t = 0;        int total = 0;        for (int i = 1; i < timeSeries.length; i++) {            t = Math.min(timeSeries[i]-timeSeries[i-1], duration);            total += t;        }        return total+duration;    }}

复杂度分析：

时间复杂度：O(n)，循环遍历数组，记数组的长度为n，故时间复杂度为O(n)。
空间复杂度：O(1)，有限两个变量分别记录前n-1个时段的持续时间和累加和，故空间复杂度为O(1)。

高防服务器 WAF 题解 oj题解 LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123045.html

leetcode每日一题-495:提莫攻击

摘要：每日一题提莫攻击链接提莫攻击题目分析从第二位开始枚举每次判断和前一次的间隔是多少然后判断出中毒的描述遍历结束后因为最后一次施加的中毒状态一定可以持续完整的中毒事件所以最后再加上代码作者 ...

kevin 2021-11-11 16:55 评论0 收藏0
【快乐水题】495. 提莫攻击

摘要：当提莫攻击艾希，艾希的中毒状态正好持续秒。正式地讲，提莫在发起发起攻击意味着艾希在时间区间含和处于中毒状态。如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在秒后结束。 ...

k00baa 2021-11-12 10:36 评论0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月汇总（109 题攻略）

摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 评论0 收藏0
JavaSE与数据结构基础知识系列——专栏导航

⭐️前面的话⭐️ 大家好！这是Java基础知识与数据结构博文的导航帖，收藏我！学习Java不迷路！ ?博客主页：未见花闻的博客主页 ?欢迎关注?点赞?收藏⭐️留言? ?本文由未见花闻原创，CSDN首发！ ?首发时间：?2021年11月11日? ✉️坚持和努力一定能换来诗与远方！ ?参考书籍：?《Java核心技术卷1》，?《Java核心技术卷2》，?《Java编程思想》 ?参考在线编程网站：?牛...

Cc_2011 2021-11-12 10:36 评论0 收藏0