文档系统

Appearance

LeetCode 933. 最近的请求次数 ​

题目链接：https://leetcode.cn/problems/number-of-recent-calls/

题目描述 ​

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

  • RecentCounter() 初始化计数器，请求数为 0
  • int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证：每次对 ping 的调用都使用比之前更大的 t 值。

示例 ​

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围 [2,3002]，返回 3
                           // 请求 1 已经不在范围内，所以移除

解题思路 ​

核心思想：滑动窗口 + 队列 ​

  1. 使用队列存储请求时间：队列的特点是先进先出（FIFO），符合时间顺序
  2. 维护时间窗口：每次 ping 时，移除所有不在 [t-3000, t] 范围内的旧请求
  3. 返回队列长度：剩余的请求数量就是答案

步骤详解 ​

步骤1：初始化一个空队列
queue = []

步骤2：每次 ping(t) 时
  ├─ 将新请求时间 t 加入队列末尾
  ├─ 检查队列头部元素
  │   └─ 如果 queue[0] < t - 3000，移除队列头部
  │   └─ 重复检查，直到队列头部元素 >= t - 3000
  └─ 返回队列的长度

步骤3：队列中保留的都是在 [t-3000, t] 范围内的请求

图解说明 ​

时间轴示例：ping(1), ping(100), ping(3001), ping(3002)

ping(1):
队列: [1]
范围: [-2999, 1]
返回: 1

ping(100):
队列: [1, 100]
范围: [-2900, 100]
返回: 2

ping(3001):
队列: [1, 100, 3001]
范围: [1, 3001]
返回: 3

ping(3002):
1 < 3002 - 3000 = 2，移除 1
队列: [100, 3001, 3002]
范围: [2, 3002]
返回: 3

JavaScript 实现 ​

方法一：使用数组模拟队列 ​

javascript
var RecentCounter = function() {
    // 初始化队列，用于存储请求时间
    this.queue = [];
};

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    // 1. 将新请求时间加入队列
    this.queue.push(t);

    // 2. 移除所有不在时间窗口 [t-3000, t] 内的请求
    while (this.queue[0] < t - 3000) {
        this.queue.shift(); // 移除队列头部元素
    }

    // 3. 返回队列长度，即有效请求数
    return this.queue.length;
};

方法二：使用原生队列（更优雅） ​

javascript
var RecentCounter = function() {
    this.requests = [];
};

RecentCounter.prototype.ping = function(t) {
    // 添加当前请求
    this.requests.push(t);

    // 移除所有早于 t-3000 的请求
    const minTime = t - 3000;
    while (this.requests.length > 0 && this.requests[0] < minTime) {
        this.requests.shift();
    }

    return this.requests.length;
};

方法三：使用ES6优化版本 ​

javascript
class RecentCounter {
    constructor() {
        this.queue = [];
    }

    ping(t) {
        this.queue.push(t);
        // 过滤掉所有不在时间窗口内的请求
        while (this.queue[0] < t - 3000) {
            this.queue.shift();
        }
        return this.queue.length;
    }
}

复杂度分析 ​

  • 时间复杂度：

    • 单次 ping 操作：均摊 O(1)
    • 虽然 while 循环可能移除多个元素，但每个元素最多被添加和移除各一次
    • 总体来说，n 次 ping 操作的总时间是 O(n)

  • 空间复杂度：O(W)，其中 W 是时间窗口内的最大请求数

    • 队列最多存储 3000ms 内的请求
    • 在最坏情况下（每毫秒都有请求），队列最多存储 3001 个元素

测试用例 ​

javascript
// 测试用例 1
const recentCounter = new RecentCounter();
console.log(recentCounter.ping(1));     // 输出: 1
console.log(recentCounter.ping(100));   // 输出: 2
console.log(recentCounter.ping(3001));  // 输出: 3
console.log(recentCounter.ping(3002));  // 输出: 3

// 测试用例 2：大量连续请求
const counter = new RecentCounter();
console.log(counter.ping(1));      // 1
console.log(counter.ping(1000));   // 2
console.log(counter.ping(2000));   // 3
console.log(counter.ping(3000));   // 4
console.log(counter.ping(4000));   // 4 (1 被移除)
console.log(counter.ping(5000));   // 4 (1, 1000 被移除，只剩 2000, 3000, 4000, 5000)

关键要点总结 ​

  1. 队列的应用：FIFO 特性天然适合处理时间序列数据
  2. 滑动窗口思想：维护固定时间范围内的数据
  3. 懒删除策略：只在需要时移除过期数据，避免不必要的操作
  4. 时间保证单调性：题目保证 t 递增，简化了问题

相关题目 ​