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)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/355251.html
標籤：其他