題目描述:Teemo 在時刻 timeSeries[0], timeSeries[1], ... 發動攻擊,每次攻擊使 Ashe 中毒 duration 秒(中毒期間重複攻擊則重設計時,即重疊部分只計一次)。計算 Ashe 的總中毒時間(秒)。
解題思路:
關鍵觀察:由於 timeSeries 已升序排列,對相鄰兩次攻擊 timeSeries[i] 和 timeSeries[i+1],第 i 次攻擊的實際中毒貢獻為:
timeSeries[i+1] - timeSeries[i] >= duration:表示第 i 次攻擊的中毒在下一次攻擊前已結束,貢獻完整的 duration。duration:下一次攻擊在中毒期間內發動,第 i 次只貢獻 timeSeries[i+1] - timeSeries[i](剩餘部分被後一次攻擊「覆蓋」重設)。最後一次攻擊沒有後繼,永遠貢獻完整的 duration。
遍歷一次陣列即可求解,時間 O(n)。
時間複雜度:O(n) — 只需單次線性掃描 timeSeries 陣列。
空間複雜度:O(1) — 只使用常數額外空間。
1. If timeSeries is empty, return 0 2. total = 0 3. For i from 0 to n-2: a. gap = timeSeries[i+1] - timeSeries[i] b. total += min(gap, duration) 4. total += duration (last attack always full) 5. Return total
區間合併法:為每次攻擊建立中毒區間 [timeSeries[i], timeSeries[i] + duration - 1],用 LC 56 合併區間後計算總長度。正確但程式碼較複雜,且空間 O(n),不如直接法簡潔。
模擬法:真正按秒模擬,記錄每秒是否中毒。值域可達 10⁷,時間 O(max_time),適合驗證正確性但不適用於競賽。
前綴和法:在值域陣列上對每次攻擊的起止位置標記差分,最後求和——概念與區間合併類似,O(V + n),適合值域小的情況。