Topic describes

Write a RecentCounter class to count the most recent requests within a specific time range.

Please implement RecentCounter class:

RecentCounter() initializes the counter with 0 requests. Int ping(int t) adds a new request at time t, where t represents some time in milliseconds, and returns the number of all requests (including new requests) that occurred in the last 3000 milliseconds. Specifically, return the number of requests that occurred within [T-3000, t]. Make sure that each call to ping uses a larger t value than before.

Analysis of the

They ask us to build a class, and then they ask us to implement a method.

Output: An instance with a method to get the problem’s request (filter the number of requests in the T-3000 range)

Their thinking

And they’re asking us to count the number of incoming requests in the t-3000 range each time we send a request, and in fact if we pass in a T, if we pass in a request that doesn’t fit the time range, then when we pass in the next T prime, it’s still going to fail, because it’s going to be further away from t’ -3000. Each time we call the ping method, we can filter out all the requests that do not meet the requirements. The rest of the requests will be in an array, and we can return the length of the array.

So we first call ping, put the incoming t into the queue, filter, shift out the unqualified, and finally return the queue length, OK.

code

var RecentCounter = function () {
  this.queue = []
}

/ * * *@param {number} t
 * @return {number}* /
RecentCounter.prototype.ping = function (t) {
  this.queue.push(t)

  while (this.queue[0] < t - 3000) {
    this.queue.shift()
  }

  return this.queue.length
}

/** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */

Copy the code

The complexity of the

Time: O(N), the length space of the queue to be traversed each time: O(N), all t needs to be stored