題目描述

在《英雄聯(lián)盟》的世界中，有一個(gè)叫 “提莫” 的英雄，他的攻擊可以讓敵方英雄艾希（編者注：寒冰射手）進(jìn)入中毒狀態(tài)。

兔寶寶提莫

現(xiàn)在，給出提莫對(duì)艾希的攻擊時(shí)間序列和提莫攻擊的中毒持續(xù)時(shí)間，你需要輸出艾希的中毒狀態(tài)總時(shí)長(zhǎng)。

你可以認(rèn)為提莫在給定的時(shí)間點(diǎn)進(jìn)行攻擊，并立即使艾希處于中毒狀態(tài)。

示例1

輸入：
[1,4], 2
輸出：
4
解釋：
在第 1 秒開(kāi)始時(shí)，提莫開(kāi)始對(duì)艾希進(jìn)行攻擊并使其立即中毒。中毒狀態(tài)會(huì)維持 2 秒鐘，直到第 2 秒鐘結(jié)束。
在第 4 秒開(kāi)始時(shí)，提莫再次攻擊艾希，使得艾希獲得另外 2 秒的中毒時(shí)間。
所以最終輸出 4 秒。

示例2

輸入：
[1,2], 2
輸出：
3
解釋：
在第 1 秒開(kāi)始時(shí)，提莫開(kāi)始對(duì)艾希進(jìn)行攻擊并使其立即中毒。中毒狀態(tài)會(huì)維持 2 秒鐘，直到第 2 秒鐘結(jié)束。
但是在第 2 秒開(kāi)始時(shí)，提莫再次攻擊了已經(jīng)處于中毒狀態(tài)的艾希。
由于中毒狀態(tài)不可疊加，提莫在第 2 秒開(kāi)始時(shí)的這次攻擊會(huì)在第 3 秒鐘結(jié)束。
所以最終輸出 3。

題解

因?yàn)閿?shù)組是時(shí)間序列，所以是給你排好序的，不需要你自己排序。

那么對(duì)于 來(lái)說(shuō)，如果 的話，就說(shuō)明前一時(shí)刻的中毒效果已經(jīng)過(guò)去了，那么當(dāng)前時(shí)刻的中毒效果持續(xù)時(shí)間都是屬于當(dāng)前時(shí)刻的，答案加上 就行了。但是如果 ，那么前一時(shí)刻的中毒效果還在，等前一時(shí)刻的中毒效果過(guò)去了，剩下的中毒時(shí)間才能算是當(dāng)前時(shí)刻的，而扣除掉上一時(shí)刻剩余的時(shí)間為 。所以最后屬于當(dāng)前時(shí)刻的中毒時(shí)間只要取 和 的最小值就行了。

最終時(shí)間復(fù)雜度為 ，空間復(fù)雜度為 。

代碼

c++

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size();
        int res = n ? duration : 0;
        for (int i = 1; i < n; ++i) {
            res += min(timeSeries[i]-timeSeries[i-1], duration);
        }
        return res;
    }
};

python

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        n = len(timeSeries)
        res = 0 if n==0 else duration
        for i in range(1, n):
            res += min(timeSeries[i]-timeSeries[i-1], duration)
        return res

后記

這題難度其實(shí)稱不上中等，選取這道題完全是因?yàn)橛形易類?ài)的小提莫！

如果有同樣喜愛(ài)英雄聯(lián)盟的召喚師（小姐姐最棒了），可以加我好友一起開(kāi)黑呀。本人艾歐尼亞（ID：godweiyang）黃金水平，雖然很菜，但是打字速度快！