495. 提莫攻击

image-20211110100157656

解题思路：

​ 一开始想着直接用set来去重，结果肯定是直接超时了。
​ 后续考虑到给出的timeSeries是非递减的形式，可以用单次遍历的方法，用t存储下当前中毒结束时间。

  • 当t<timeSeries[i]+duration时，表示着这个结束时间需要刷新，因此先对结果res+=timeSeries[i]+duration-t-max(timeSeries[i]-t,0) (后续的max是因为考虑到若中途有非中毒时间要减去)，同时更新t=timeSeries[i]+duration

以下为C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        //用hashset记录下时间节点去重，最后获取其size()即可获得秒数（超时）
        // set<int> s;
        // int len=timeSeries.size();
        // for(int i=0;i<len;i++){
        //     for(int j=0;j<duration;j++){
        //         s.insert(timeSeries[i]+j);
        //     }
        // }
        // return s.size();

        //遍历时记录下实际中毒的最大秒数
        int t=0;
        int res=0;
        int len=timeSeries.size();
        for(int i=0;i<len;i++){
            if(t<timeSeries[i]+duration){
                res+=timeSeries[i]+duration-t-max(timeSeries[i]-t,0);
                t=timeSeries[i]+duration;
            }
        }
        return res;
    }
};