495.提莫攻击.md

495. 提莫攻击

https://leetcode-cn.com/problems/teemo-attacking/

一、暴力（超时）

用一个count数组记录i秒中毒的总次数，遍历所有time序列，对[time ... time+duration-1]部分的count加一。

最后再看count[i] != 0的个数即可。0 <= timeSeries[i], duration <= 10^7，则i最大为2000000

class Solution:
    def findPoisonedDuration(self, timeSeries, duration) -> int:
        count = [0] * 20000000
        for time in timeSeries:
            for i in range(duration):
                count[time + i] += 1
        res = 0
        for i in range(20000000):
            if count[i]:
                res += 1
        return res

二、暴力+优化

中毒时间会重叠，没必要重复计算。由于time序列非递减，因此直接遍历即可模拟时间正向，用now表示当前时间，每次now = time + duration。用count记录中毒时间总数

time与now只有两种情况：1）重叠，即time < now ；否则为2）不重叠。因为time序列非递减，不会有其他情况

重叠时count增量为duration - (now - time)，画图可知

不重叠增量直接为duration

class Solution:
    def findPoisonedDuration(self, timeSeries, duration) -> int:
        now = 0
        count = 0
        for time in timeSeries:
            if time < now:
                count += duration - (now - time)
            else:
                count += duration
            now = time + duration
        return count