最近的请求次数

难度: Easy

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

请你实现 RecentCounter 类：

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

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

示例 1：

输入：
["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 <= t <= 10⁹
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 10⁴ 次

Submission

运行时间: 170 ms

内存: 21.9 MB

class RecentCounter:


    def __init__(self):
        self.nums = []

    def ping(self, t):

        self.nums.append(t)
        cur_pos = len(self.nums)
        prev_pos = bisect.bisect_left(self.nums, t - 3000)
        return cur_pos - prev_pos

# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

Explain

RecentCounter 类通过使用列表来记录每次的 ping 请求时间。ping 方法被调用时，会将时间 t 添加到列表，并利用二分查找方法找出过去 3000 毫秒内（包括当前时间 t）所有的请求。使用 bisect.bisect_left 函数找出 t-3000 在列表中应插入的位置，这个位置也表示了所有在 t-3000 后发生的请求的起始位置。通过计算当前列表长度与这个位置的差，我们可以得到 t-3000 到 t 时间范围内的请求总数。

时间复杂度: O(log n)

空间复杂度: O(n)

class RecentCounter:

    def __init__(self):
        self.nums = []  # 初始化列表以存储每次 ping 的时间点

    def ping(self, t):
        self.nums.append(t)  # 添加当前时间点 t 到列表
        cur_pos = len(self.nums)  # 获取当前列表的长度
        prev_pos = bisect.bisect_left(self.nums, t - 3000)  # 使用二分查找确定 t-3000 在列表中的位置
        return cur_pos - prev_pos  # 返回在时间范围 [t-3000, t] 内的请求总数

Explore

在使用 `bisect.bisect_left` 函数时，该函数会返回在排序列表中第一个大于等于指定值（此处为 t-3000）的元素的位置。如果列表中存在元素等于 t-3000，`bisect_left` 将返回该元素的位置；如果不存在，将返回第一个大于 t-3000 的元素的位置。这确保了我们得到的 `prev_pos` 是过去 3000 毫秒内第一个请求的位置，从而包括了所有从 t-3000 到 t 时间内的请求。

随着 `RecentCounter` 类中的 `nums` 列表不断增长，两个主要的性能问题会逐渐显现：一是列表所占内存空间会持续增加，可能导致内存使用效率低下；二是每次调用 `ping(t)` 方法时，使用 `bisect_left` 进行二分查找的时间复杂度虽然是 O(log n)，但随着列表长度的增加，查找效率会下降。此外，列表每次增加元素（append 操作）的时间复杂度为 O(1)，但总体上要考虑查找和空间占用带来的综合性能影响。

当 `bisect.bisect_left` 用于查找元素 t-3000 时，如果列表中没有精确匹配的元素，该函数将返回应该插入 t-3000 以保持列表排序的位置索引。这个位置表示的是列表中第一个大于 t-3000 的元素的索引，确保了所有 t-3000 之后（包括 t-3000 时刻）的请求都被正确计算。