题目描述
在《英雄联盟》的世界中,有一个叫“提莫”的英雄,他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。现在,给出提莫对艾希的攻击的递增时间序列和提莫攻击的中毒持续时间,你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击,并立即使艾希处于中毒状态。
样例
输入:[1,4], 2
输出:4
解释:在第 1 秒开始时,提莫开始对艾希进行攻击并使其立即中毒。
中毒状态会维持2秒钟,直到第 2 秒钟结束。
在第 4 秒开始时,提莫再次攻击艾希,使得艾希获得另外 2 秒的中毒时间。
所以最终输出 4 秒。
输入:[1,2], 2
输出:3
解释:在第 1 秒开始时,提莫开始对艾希进行攻击并使其立即中毒。
中毒状态会维持 2 秒钟,直到第 2 秒钟结束。
但是在第 2 秒开始时,提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加,提莫在第 2 秒开始时的这次攻击会在第 3 秒钟结束。
所以最终输出 3。
注意
- 你可以假定时间序列数组的总长度不超过 10000。
- 你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数,并且不超过 10,000,000。
算法
(模拟) $O(n)$
- 将时间序列的每个时间点扩展为开始时间和结束时间,然后求这些区间并集的总长度。
时间复杂度
- 仅遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int n = timeSeries.size();
int ans = 0, start = 0, end = -1;
for (int i = 0; i < n; i++) {
int s = timeSeries[i], e = s + duration - 1;
if (end < s) {
ans += end - start + 1;
start = s;
end = e;
}
end = max(end, e);
}
ans += end - start + 1;
return ans;
}
};
start 和end 设置的很巧妙,避免了在循环中的讨论。👍