剑指 Offer II 042. 最近请求次数

队列
因为需要使用到时间 t 之前的时间，所以将每次的时间都存入一个容器中。

当输入到时间 t 时，有效的时间为 [t-3000, t]，所以只要去掉容器中所有小于 t-3000的时间即可。

因为时间越来越大，所以越早输入的越小，根据存入容器的先后顺序判断时间是否符合，不符合则将其从容器中删除，直到遍历到符合要求的时间为止，停止删除。

可以发现容器需要符合"先入先出" 的规则，故使用队列保存时间。

每次 ping *** 作的时间复杂度是 O(1)，空间复杂度为 O(1)。

c++实现

class RecentCounter {
private:
    int slot;
    queue<int> time;
public:
    RecentCounter() {
        slot = 3000;
    }
    
    int ping(int t) {
        time.push(t);
        int early = t-slot;
        while (time.front()<early){
            time.pop();
        }
        return time.size();
    }
};

golang实现

type RecentCounter struct {
    slot int
    time []int
}

func Constructor() RecentCounter {
    return RecentCounter{
        slot : 3000,
        time : []int{}}
}

func (this *RecentCounter) Ping(t int) int {
    this.time =append(this.time,t)
    early := t-this.slot
    for this.time[0] < early {
        this.time = this.time[1:]
    }
    return len(this.time)
}