题目：最近的请求次数

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/H8086Q

  1. // 输入
  2. inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
  3. inputs = [[], [1], [100], [3001], [3002]]
  5. // 输出
  6. [null, 1, 2, 3, 3]
  8. // 解释
  9. RecentCounter recentCounter = new RecentCounter();
  10. recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
  11. recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
  12. recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
  13. recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

理解题意

输入时间数量，单位为ms，返回在当前时间内会发出的请求数量。
比如说输入1，那么因为范围在 [t - 3000, t]之间，范围就是[-2999, 1]，包含了1；所以请求一次
接着输入100，那么范围在[-2900, 100]，因为包含了上次输入的1和本次的100; 所以请求次数为两次

  • 保证每次对ping的调用都使用比之前更大的t值
  • 每个测试用例会使用严格递增的t值来调用ping，最多调用1000次ping
  1. 下一次输入的时间的大小一定会大于上一次输入时间，也就是说t是一个递增的关系

  2. 每次请求都会执行ping方法，该方法返回t时间点及此前3000ms内的请求总次数(包含t时间点和t-3000时间点)

    数据结构及算法思维的选择

    数据结构：数组
    算法思维：遍历

    基本解法及编码的实现

    暴力解法：

  3. 创建数组，存放所有请求

    1. 整型数组，存放10000个元素
  4. 把当前请求存入数组
    1. 记录最后一次存入的索引，从零开始

  5. 统计距离此次请求前3000ms之间的请求次数

    1. 从最后一次存放位置倒序遍历

      class RecentCounter {
array: number[];
constructor() {
this.array = []; // 创建数组，存放所有请求。 因为js数组是可以动态扩容的
}
ping(t: number): number {
let end = 0; // 最近一次请求的开始索引，从零开始
for (let i = 0; i < 10 ** 4; i++) {
if (!this.array[i]) {  // 数组为空的时候没有存放任何请求
  this.array[i] = t;
  end = i; // 记录最近一次操作的索引
  break;
}
};

let count = 0; // 计数器
while(this.array[end] >= (t - 3000)) { // 数组元素要在要求的范围内    
count++;
if (--end < 0) { // 倒序遍历 防止越界
  break;
}
}
return count
}
}

      时间复杂度：O(n ^ 2)

  • 存入数组，每次遍历n-1个位置：O(n - 1)
  • 统计请求次数，每次遍历1 ~ n个位置：O(n)
  • ping方法会调用n次：n(n - 1 + n) —> n ^ 2

空间复杂度：O(1)

  • 固定10000长度的数组开销空间复杂度：O(1)
  • 空间消耗很大

    思考最优解

  1. 剔除无效代码或优化空间消耗
    1. 创建成千上万个容量的数组比较浪费空间，能够动态扩展容器的容量
    2. 是否有其它更方便的数据结构
  2. 寻找更好的算法思维
    1. 精准计算首尾指针的索引容易出错
    2. 借鉴其它算法

      最优解思路及编码实现

      出现不满足数据的时候，后续的再添加的操作就再也不满足，可以直接删除掉不满足的数据。例如：依次输入1、100、3001、3002、3010，输入的答案应该是1,2,3,3,4 。因为3002的时候操作t为1的不再满足后续的操作了，可以把1这个数据删掉，也就是说，动态增删输入数组，每次有新数据push进来，检查删除掉不合法的t就行，直接返回数组的长度，就是最近的操作次数。

队列

  1. 数据结构选择：队列
    1. 始终在一端插入数据，另一端删除数据
    2. 先进先出
    3. 插入和删除时间复杂度：O(1)
  2. 基本操作
    1. 入队
    2. 出队

最优解：
队列解法思路分析

  1. 使用链表实现一个队列
    1. 定义属性：队头、队尾、长度
    2. 定义方法：添加节点、移除节点、队列长度
    3. 定义内部类：封装每次入队的请求数据和指向下一个节点的指针
  2. 每次请求向队列尾部追加节点
  3. 循环检查头部数据是否合法，不合法则移除节点
  4. 返回队列长度

边界细节问题和复杂度分析

  • 边界问题
    • 入队和出队始终关注首尾节点指针

  • 细节问题

    • 第一次添加节点，首尾指针都是null
    • 每次追加尾节点，size++，重置tail
    • 每次移除头结点，size—，重置head ```typescript class RecentCounter { array: number[]; constructor() { this.array = []; }

    ping(t: number): number { this.array.push(t); // 主要是借助js特性完成了队列的思想

    while(this.array[0] < (t - 3000)) {

    this.array.shift();

    };

    return this.array.length; } } ``` 时间复杂度：O(n)

  • 添加和删除元素为1

  • ping方法调用n次

空间复杂度: O(1)

  • 每次添加都是1

  • 最多保留3001个元素，所以空间复杂度为： 1 ~ 3001 即O(1)

    变形延伸

  • 数组 + 双指针模式也是队列的另一种存在方式

总结

队列的特点：

  1. 始终在一端插入数据，另一端删除数据
  2. 先进先出
  3. 插入和删除时间复杂度：O(1)

    队列的应用：

  • 生产者消费者模式：CPU调度多线程；消息队列，作为缓冲区提高效率