LeetCode-Go 題解 495Teemo Attacking提莫攻擊——中毒區間的合并累計與貪心掃描【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go導讀LeetCode 495 題 Teemo Attacking提莫攻擊是一道經典的數組區間合并類問題給定一組非遞減的攻擊時間戳與固定的中毒持續時間求敵方英雄處于中毒狀態的總秒數。本篇文章以 leetcode/0495.Teemo-Attacking/README.md 的官方題解為骨架結合 LeetCode-Go 倉庫中的 Go 實現源碼 與單元測試完整講解題目語義、區間重疊判斷的關鍵邊界、單次線性掃描的貪心解法及其復雜度證明并給出可直接運行驗證的代碼與測試命令。讀完本文你將掌握區間合并 相鄰差量累計這類時間軸問題的通用思考方式并能獨立寫出 O(n) 時間、O(1) 空間的解決方案。一、題目背景與完整描述本題的背景取自 MOBA 游戲《英雄聯盟》英雄提莫Teemo攻擊敵方艾希Ashe寒冰射手后艾希會進入持續duration秒的中毒狀態。題目原文描述如下Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for exactlydurationseconds.More formally, an attack at secondtwill mean Ashe is poisoned during the inclusive time interval[t, t duration - 1].If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will enddurationseconds after the new attack.You are given a non-decreasing integer arraytimeSeries, wheretimeSeries[i]denotes that Teemo attacks Ashe at secondtimeSeries[i], and an integerduration.Return the total number of seconds that Ashe is poisoned.用中文概括題意為提莫在t秒發起攻擊意味著艾希在閉區間[t, t duration - 1]含兩端內處于中毒狀態如果提莫在本次中毒效果結束之前再次攻擊中毒計時器會被重置新的攻擊之后中毒狀態將再持續duration秒輸入是一個非遞減的整數數組timeSeriestimeSeries[i]表示第i次攻擊發生在第timeSeries[i]秒和一個整數duration要求返回艾希處于中毒狀態的總秒數。二、示例推演理解重置語義原題解給出了兩個極具代表性的示例先完整過一遍示例 1timeSeries [1,4], duration 2輸出4- 第 1 秒提莫攻擊艾希在第 1、2 秒中毒 - 第 4 秒提莫攻擊艾希在第 4、5 秒中毒。 艾希在第 1、2、4、5 秒處于中毒狀態總計 4 秒。兩次攻擊第 1 秒與第 4 秒之間間隔 3 秒大于duration - 1 1上一次中毒第 2 秒結束后下一次攻擊第 4 秒才開始兩個中毒區間完全不重疊因此總時長直接相加2 2 4。示例 2timeSeries [1,2], duration 2輸出3- 第 1 秒提莫攻擊艾希在第 1、2 秒中毒 - 第 2 秒提莫再次攻擊并重置中毒計時器艾希在第 2、3 秒中毒。 艾希在第 1、2、3 秒處于中毒狀態總計 3 秒。第 1 秒的攻擊使艾希中毒到第 2 秒而第 2 秒的攻擊發生在中毒尚未結束時計時器被重置中毒延續到第 3 秒。兩個中毒區間[1, 2]與[2, 3]首尾相接、發生重疊合并后為[1, 3]共 3 秒而不是簡單的2 2 4。這正是本題與樸素累加的差異所在重疊部分不能重復計數。三、約束條件與邊界意識原題給定的約束如下1 timeSeries.length 100000 timeSeries[i], duration 10000000timeSeries按非遞減順序排列從約束可以提煉出三個對實現有直接影響的點數組長度最大 10000O(n) 的線性掃描完全夠用任何 O(n2) 的雙重循環都不必要duration可以為 0當duration 0時每次攻擊不產生任何中毒時間代碼必須能正確處理返回 0攻擊時間戳允許重復非遞減而非嚴格遞增timeSeries[i] timeSeries[i-1]是合法輸入此時屬于完全重疊區間合并邏輯必須覆蓋這種情況。四、核心思路把問題抽象成區間合并 相鄰差量累計4.1 問題本質是一維閉區間合并每次攻擊產生一個長度為duration的閉區間[t, t duration - 1]。題目要求的中毒總秒數本質就是這些區間并集的長度。由于攻擊時間戳按非遞減排列區間在時間軸上天然有序因此可以用單次掃描完成合并計數不需要排序也不需要記錄所有區間。4.2 相鄰兩次攻擊只有兩種關系設當前正在考察的是第i-1次攻擊時間t timeSeries[i-1]與第i次攻擊時間timeSeries[i]并記end t duration - 1為第i-1次攻擊造成的中毒結束時刻。兩種情形為區間斷開end timeSeries[i]上一次中毒在下次攻擊之前就已結束兩次中毒完全獨立。前一次攻擊應完整計入duration秒區間重疊end timeSeries[i]下次攻擊發生時中毒仍在持續計時器重置。此時從第i-1次攻擊到第i次攻擊之間新增的中毒時間是timeSeries[i] - t秒從t秒到timeSeries[i]秒前一刻而timeSeries[i]這一秒起的中毒時間將交給最后一次攻擊的完整duration統一兜底。4.3 關鍵邊界為什么必須是嚴格小于end timeSeries[i]注意中毒區間是閉區間[t, t duration - 1]。當end timeSeries[i]時即下一次攻擊恰好發生在上一次中毒的最后一秒例如timeSeries [1, 2], duration 2第 1 秒攻擊中毒區間[1, 2]第 2 秒攻擊觸發重置合并后總時長為timeSeries[i] - t duration 2 - 1 2 3秒與示例 2 的輸出完全一致。因此在判斷時必須使用end timeSeries[i]嚴格小于判定為斷開而end timeSeries[i]含相等一律按重疊處理。若誤寫成end timeSeries[i]示例 2 會被錯誤地算成2 2 4秒。五、Go 實現來自倉庫的完整解法原題解給出的核心解法如下源碼位于 495.Teemo Attacking.gopackage leetcode func findPoisonedDuration(timeSeries []int, duration int) int { var ans int for i : 1; i len(timeSeries); i { t : timeSeries[i-1] end : t duration - 1 if end timeSeries[i] { ans duration } else { ans timeSeries[i] - t } } ans duration return ans }逐段解讀算法流程循環從i 1開始每次考察相鄰的兩次攻擊timeSeries[i-1]與timeSeries[i]記t timeSeries[i-1]end t duration - 1為上一次攻擊的中毒結束時刻閉區間右端點若end timeSeries[i]區間斷開上一次攻擊完整貢獻duration秒ans duration否則區間重疊含首尾相接只累計到下一次攻擊前的新增部分timeSeries[i] - t秒循環結束后最后一次攻擊必定產生一個完整的duration秒中毒區間因此最后統一ans duration并返回。用示例 2 走一遍timeSeries [1,2], duration 2。i 1t 1end 1 2 - 1 2end timeSeries[1] 2走重疊分支ans 2 - 1 1循環結束ans duration 2總ans 3輸出正確。六、等價寫法與復雜度分析6.1 更緊湊的等價寫法上面的分支判斷可以用min函數等價壓縮區間斷開時duration timeSeries[i] - t重疊時duration timeSeries[i] - t因此每次累計的新增時長恰好是兩者的較小值func findPoisonedDuration(timeSeries []int, duration int) int { ans : 0 for i : 1; i len(timeSeries); i { ans min(duration, timeSeries[i]-timeSeries[i-1]) } return ans duration }兩種寫法在數學上完全等價區別只是風格。倉庫當前的 go.mod 聲明go 1.19在該版本下min尚不是內建函數因此原題解使用顯式的if/else分支避免引入額外依賴這一點也體現了實現上的版本兼容考量。6.2 復雜度時間復雜度 O(n)單次線性掃描n為timeSeries的長度與時間戳的絕對數值大小無關空間復雜度 O(1)只使用常數個變量不依賴額外存儲。即便輸入規模達到約束上限長度 10000、時間戳 10^7也能在微秒量級內完成計算不存在溢出風險t duration最大約 2×10^7遠小于int上限。七、測試驗證倉庫測試用例與運行方式7.1 倉庫內建的兩個用例倉庫在 495.Teemo Attacking_test.go 中為本題提供了與題解示例一一對應的測試用例輸入timeSeries輸入duration期望輸出[1, 4]24[1, 2]23測試代碼通過Test_Problem495遍歷用例表并打印輸入輸出覆蓋了區間斷開與區間重疊首尾相接兩條核心路徑。你可以補充更多邊界用例自行驗證例如timeSeries [1], duration 5→ 單次攻擊輸出5對應循環體一次都不執行、最后ans duration的分支timeSeries [1, 1], duration 2→ 攻擊時間戳重復區間完全重疊輸出2timeSeries [1, 2, 3], duration 2→ 連續攻擊不斷重置計時器輸出4合并區間[1, 4]。7.2 如何運行測試倉庫根目錄的 gotest.sh 定義了全量測試方式其核心命令是對所有題解包做覆蓋率測試go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...單獨驗證本題時可以只運行本題目錄下的測試go test -v ./leetcode/0495.Teemo-Attacking/倉庫在根目錄維護了 coverage.txt 覆蓋率文件并在項目描述中宣稱 100% 測試覆蓋測試基建含覆蓋率收集腳本由 gotest.sh 統一支撐因此本題實現同樣受到該機制的約束與驗證。八、總結LeetCode 495Teemo Attacking的核心價值在于把一個帶重置語義的時間軸計數問題轉化為有序閉區間的并集長度計算攻擊序列非遞減保證了相鄰區間有序使單次掃描成為可能判斷重疊時務必注意閉區間特性用end timeSeries[i]嚴格小于判定斷開end timeSeries[i]含端點重合判定重疊每次迭代只累計相鄰兩次攻擊之間的新增時長最后一次攻擊的完整duration在循環外統一追加從而規避重復計數整體解法為 O(n) 時間、O(1) 空間與 LeetCode-Go 倉庫其他題解的風格一致并配有可直接運行的 單元測試 佐證正確性。掌握這一相鄰差量累計 收尾兜底的模式后遇到形如區間合并、覆蓋時長統計、時間軸去重等一類問題都可以快速套用同樣的思維框架。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考 LeetCode-Go 題解 495：Teemo Attacking（提莫攻擊）——中毒區間的合并累計與貪心掃描
LeetCode-Go 題解 495Teemo Attacking提莫攻擊——中毒區間的合并累計與貪心掃描【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go導讀LeetCode 495 題 Teemo Attacking提莫攻擊是一道經典的數組區間合并類問題給定一組非遞減的攻擊時間戳與固定的中毒持續時間求敵方英雄處于中毒狀態的總秒數。本篇文章以 leetcode/0495.Teemo-Attacking/README.md 的官方題解為骨架結合 LeetCode-Go 倉庫中的 Go 實現源碼 與單元測試完整講解題目語義、區間重疊判斷的關鍵邊界、單次線性掃描的貪心解法及其復雜度證明并給出可直接運行驗證的代碼與測試命令。讀完本文你將掌握區間合并 相鄰差量累計這類時間軸問題的通用思考方式并能獨立寫出 O(n) 時間、O(1) 空間的解決方案。一、題目背景與完整描述本題的背景取自 MOBA 游戲《英雄聯盟》英雄提莫Teemo攻擊敵方艾希Ashe寒冰射手后艾希會進入持續duration秒的中毒狀態。題目原文描述如下Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for exactlydurationseconds.More formally, an attack at secondtwill mean Ashe is poisoned during the inclusive time interval[t, t duration - 1].If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will enddurationseconds after the new attack.You are given a non-decreasing integer arraytimeSeries, wheretimeSeries[i]denotes that Teemo attacks Ashe at secondtimeSeries[i], and an integerduration.Return the total number of seconds that Ashe is poisoned.用中文概括題意為提莫在t秒發起攻擊意味著艾希在閉區間[t, t duration - 1]含兩端內處于中毒狀態如果提莫在本次中毒效果結束之前再次攻擊中毒計時器會被重置新的攻擊之后中毒狀態將再持續duration秒輸入是一個非遞減的整數數組timeSeriestimeSeries[i]表示第i次攻擊發生在第timeSeries[i]秒和一個整數duration要求返回艾希處于中毒狀態的總秒數。二、示例推演理解重置語義原題解給出了兩個極具代表性的示例先完整過一遍示例 1timeSeries [1,4], duration 2輸出4- 第 1 秒提莫攻擊艾希在第 1、2 秒中毒 - 第 4 秒提莫攻擊艾希在第 4、5 秒中毒。 艾希在第 1、2、4、5 秒處于中毒狀態總計 4 秒。兩次攻擊第 1 秒與第 4 秒之間間隔 3 秒大于duration - 1 1上一次中毒第 2 秒結束后下一次攻擊第 4 秒才開始兩個中毒區間完全不重疊因此總時長直接相加2 2 4。示例 2timeSeries [1,2], duration 2輸出3- 第 1 秒提莫攻擊艾希在第 1、2 秒中毒 - 第 2 秒提莫再次攻擊并重置中毒計時器艾希在第 2、3 秒中毒。 艾希在第 1、2、3 秒處于中毒狀態總計 3 秒。第 1 秒的攻擊使艾希中毒到第 2 秒而第 2 秒的攻擊發生在中毒尚未結束時計時器被重置中毒延續到第 3 秒。兩個中毒區間[1, 2]與[2, 3]首尾相接、發生重疊合并后為[1, 3]共 3 秒而不是簡單的2 2 4。這正是本題與樸素累加的差異所在重疊部分不能重復計數。三、約束條件與邊界意識原題給定的約束如下1 timeSeries.length 100000 timeSeries[i], duration 10000000timeSeries按非遞減順序排列從約束可以提煉出三個對實現有直接影響的點數組長度最大 10000O(n) 的線性掃描完全夠用任何 O(n2) 的雙重循環都不必要duration可以為 0當duration 0時每次攻擊不產生任何中毒時間代碼必須能正確處理返回 0攻擊時間戳允許重復非遞減而非嚴格遞增timeSeries[i] timeSeries[i-1]是合法輸入此時屬于完全重疊區間合并邏輯必須覆蓋這種情況。四、核心思路把問題抽象成區間合并 相鄰差量累計4.1 問題本質是一維閉區間合并每次攻擊產生一個長度為duration的閉區間[t, t duration - 1]。題目要求的中毒總秒數本質就是這些區間并集的長度。由于攻擊時間戳按非遞減排列區間在時間軸上天然有序因此可以用單次掃描完成合并計數不需要排序也不需要記錄所有區間。4.2 相鄰兩次攻擊只有兩種關系設當前正在考察的是第i-1次攻擊時間t timeSeries[i-1]與第i次攻擊時間timeSeries[i]并記end t duration - 1為第i-1次攻擊造成的中毒結束時刻。兩種情形為區間斷開end timeSeries[i]上一次中毒在下次攻擊之前就已結束兩次中毒完全獨立。前一次攻擊應完整計入duration秒區間重疊end timeSeries[i]下次攻擊發生時中毒仍在持續計時器重置。此時從第i-1次攻擊到第i次攻擊之間新增的中毒時間是timeSeries[i] - t秒從t秒到timeSeries[i]秒前一刻而timeSeries[i]這一秒起的中毒時間將交給最后一次攻擊的完整duration統一兜底。4.3 關鍵邊界為什么必須是嚴格小于end timeSeries[i]注意中毒區間是閉區間[t, t duration - 1]。當end timeSeries[i]時即下一次攻擊恰好發生在上一次中毒的最后一秒例如timeSeries [1, 2], duration 2第 1 秒攻擊中毒區間[1, 2]第 2 秒攻擊觸發重置合并后總時長為timeSeries[i] - t duration 2 - 1 2 3秒與示例 2 的輸出完全一致。因此在判斷時必須使用end timeSeries[i]嚴格小于判定為斷開而end timeSeries[i]含相等一律按重疊處理。若誤寫成end timeSeries[i]示例 2 會被錯誤地算成2 2 4秒。五、Go 實現來自倉庫的完整解法原題解給出的核心解法如下源碼位于 495.Teemo Attacking.gopackage leetcode func findPoisonedDuration(timeSeries []int, duration int) int { var ans int for i : 1; i len(timeSeries); i { t : timeSeries[i-1] end : t duration - 1 if end timeSeries[i] { ans duration } else { ans timeSeries[i] - t } } ans duration return ans }逐段解讀算法流程循環從i 1開始每次考察相鄰的兩次攻擊timeSeries[i-1]與timeSeries[i]記t timeSeries[i-1]end t duration - 1為上一次攻擊的中毒結束時刻閉區間右端點若end timeSeries[i]區間斷開上一次攻擊完整貢獻duration秒ans duration否則區間重疊含首尾相接只累計到下一次攻擊前的新增部分timeSeries[i] - t秒循環結束后最后一次攻擊必定產生一個完整的duration秒中毒區間因此最后統一ans duration并返回。用示例 2 走一遍timeSeries [1,2], duration 2。i 1t 1end 1 2 - 1 2end timeSeries[1] 2走重疊分支ans 2 - 1 1循環結束ans duration 2總ans 3輸出正確。六、等價寫法與復雜度分析6.1 更緊湊的等價寫法上面的分支判斷可以用min函數等價壓縮區間斷開時duration timeSeries[i] - t重疊時duration timeSeries[i] - t因此每次累計的新增時長恰好是兩者的較小值func findPoisonedDuration(timeSeries []int, duration int) int { ans : 0 for i : 1; i len(timeSeries); i { ans min(duration, timeSeries[i]-timeSeries[i-1]) } return ans duration }兩種寫法在數學上完全等價區別只是風格。倉庫當前的 go.mod 聲明go 1.19在該版本下min尚不是內建函數因此原題解使用顯式的if/else分支避免引入額外依賴這一點也體現了實現上的版本兼容考量。6.2 復雜度時間復雜度 O(n)單次線性掃描n為timeSeries的長度與時間戳的絕對數值大小無關空間復雜度 O(1)只使用常數個變量不依賴額外存儲。即便輸入規模達到約束上限長度 10000、時間戳 10^7也能在微秒量級內完成計算不存在溢出風險t duration最大約 2×10^7遠小于int上限。七、測試驗證倉庫測試用例與運行方式7.1 倉庫內建的兩個用例倉庫在 495.Teemo Attacking_test.go 中為本題提供了與題解示例一一對應的測試用例輸入timeSeries輸入duration期望輸出[1, 4]24[1, 2]23測試代碼通過Test_Problem495遍歷用例表并打印輸入輸出覆蓋了區間斷開與區間重疊首尾相接兩條核心路徑。你可以補充更多邊界用例自行驗證例如timeSeries [1], duration 5→ 單次攻擊輸出5對應循環體一次都不執行、最后ans duration的分支timeSeries [1, 1], duration 2→ 攻擊時間戳重復區間完全重疊輸出2timeSeries [1, 2, 3], duration 2→ 連續攻擊不斷重置計時器輸出4合并區間[1, 4]。7.2 如何運行測試倉庫根目錄的 gotest.sh 定義了全量測試方式其核心命令是對所有題解包做覆蓋率測試go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...單獨驗證本題時可以只運行本題目錄下的測試go test -v ./leetcode/0495.Teemo-Attacking/倉庫在根目錄維護了 coverage.txt 覆蓋率文件并在項目描述中宣稱 100% 測試覆蓋測試基建含覆蓋率收集腳本由 gotest.sh 統一支撐因此本題實現同樣受到該機制的約束與驗證。八、總結LeetCode 495Teemo Attacking的核心價值在于把一個帶重置語義的時間軸計數問題轉化為有序閉區間的并集長度計算攻擊序列非遞減保證了相鄰區間有序使單次掃描成為可能判斷重疊時務必注意閉區間特性用end timeSeries[i]嚴格小于判定斷開end timeSeries[i]含端點重合判定重疊每次迭代只累計相鄰兩次攻擊之間的新增時長最后一次攻擊的完整duration在循環外統一追加從而規避重復計數整體解法為 O(n) 時間、O(1) 空間與 LeetCode-Go 倉庫其他題解的風格一致并配有可直接運行的 單元測試 佐證正確性。掌握這一相鄰差量累計 收尾兜底的模式后遇到形如區間合并、覆蓋時長統計、時間軸去重等一類問題都可以快速套用同樣的思維框架。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考