933. Number of Recent Calls

Задача

Реализуйте класс RecentCounter: метод ping(t) возвращает число запросов за последние 3000 мс.

Примеры

Пример 1

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Решение

Решение

var RecentCounter = function() {
    this.requests = [];
    this.lastUsedIndex = 0;
};
 
// Временная сложность: O(1) — (амортизированная). Каждый элемент добавляется 1 раз и "пропускается" циклом 1 раз.
// Пространственная сложность: O(N) — где N это ОБЩЕЕ количество вызовов ping за всё время (из-за того, что мы не чистим массив).
RecentCounter.prototype.ping = function(t) {
    this.requests.push(t);
 
    const rangeStart = t - 3000; // Math.max не обязателен, условие >= сработает и так
 
    // Мы двигаем указатель вперед, пропуская устаревшие элементы
    for (let i = this.lastUsedIndex; i < this.requests.length; i++) {
        if (this.requests[i] >= rangeStart) {
            this.lastUsedIndex = i;
            return this.requests.length - this.lastUsedIndex;
        }
    }
 
    return null;
}

Решение 1

var RecentCounter = function() {
    this.requests = [];
};
 
// Временная сложность: O(1) амортизированная
// Пространственная сложность: O(W) где W — ширина окна (максимум ~3000 элементов в массиве одновременно)
RecentCounter.prototype.ping = function(t) {
    this.requests.push(t);
    while (this.requests[0] < t - 3000) {
        this.requests.shift();
    }
    return this.requests.length;
};