提莫攻击

难度:

标签:

题目描述

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

当提莫攻击艾希，艾希的中毒状态正好持续 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 。

提示：

1 <= timeSeries.length <= 10⁴
0 <= timeSeries[i], duration <= 10⁷
timeSeries 按 非递减 顺序排列

代码结果

运行时间: 33 ms, 内存: 17.0 MB

/*
 * 思路：
 * 使用Java Stream来计算提莫的总中毒时间。
 * 使用stream中的IntStream进行映射，每次映射的结果是两次攻击之间的时间差和持续时间中的最小值，
 * 最后通过sum来计算总的中毒时间，再加上最后一次攻击的持续时间。
 */
 
import java.util.Arrays;
 
public class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries == null || timeSeries.length == 0) return 0;
        int totalDuration = Arrays.stream(timeSeries, 0, timeSeries.length - 1)
                .map(i -> Math.min(timeSeries[i + 1] - timeSeries[i], duration))
                .sum();
        return totalDuration + duration;
    }
}

解释

方法:

该题解的思路是使用区间合并的方法。遍历timeSeries数组，对于当前攻击时间t，计算出中毒的区间[i, j)，其中i=t, j=t+duration。然后判断当前区间是否与前一个中毒区间[pre_i, pre_j)重叠，如果pre_j > i，说明两个区间有重叠部分，可以将它们合并，更新pre_j为max(pre_j, j)；否则两个区间没有重叠，将前一个区间的时间累加到total，然后更新pre_i和pre_j为当前区间的起止时间。遍历结束后，将最后一个区间的时间也累加到total。最终返回total即可。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么选择使用区间合并的方法来解决这个问题？

▷

区间合并方法是解决此问题的理想选择，因为它能有效处理时间序列中的重叠中毒效果。每次提莫攻击都可能在前一个攻击的中毒效果尚未结束时发生，造成中毒时间的重叠。使用区间合并方法，可以通过判断当前的攻击开始时间是否在前一个中毒时间段之内来决定是否需要合并区间，从而避免重复计算中毒时间，确保每段中毒时间只被计算一次。这样不仅提高了算法的效率，还保证了计算的准确性。

🦆

题解中提到的中毒区间是左闭右开区间[i, j)，这种表示对最后结果的计算有什么影响？

▷

在题解中使用左闭右开的区间[i, j)表示中毒时间段主要是为了方便区间的合并和计算。在这种表示方式下，当一个中毒区间结束的时间恰好是另一个中毒区间开始的时间（即i等于前一个区间的j），这两个区间实际上是不重叠的。这样的表示方式简化了区间合并的判断逻辑，只需检查当前区间的开始时间i是否小于上一个区间的结束时间j来决定是否合并。这种表示还便于计算每个独立中毒区间的时长，直接用j - i即可得到正确的中毒时长，无需额外的处理或调整。

相关问题

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

提示：

1 <= flowerbed.length <= 2 * 10⁴
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length

Dota2 参议院

Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。

给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。

示例 1：

输入：senate = "RD"
输出："Radiant"
解释：
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。

示例 2：

输入：senate = "RDD"
输出："Dire"
解释：
第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

提示：

n == senate.length
1 <= n <= 10⁴
senate[i] 为 'R' 或 'D'

目标和下一个更大元素 I