How do I efficiently track recent calls for the Number of Recent Calls problem?

Using a queue is an efficient way to track recent calls, as it allows constant-time access to the count of recent requests within a specified time window.

What is the time complexity of the solution for the Number of Recent Calls problem?

The time complexity of each ping operation is O(1) on average, due to the efficient use of a queue to manage the time window of requests.

Can the queue-based solution handle the maximum input size?

Yes, the queue-based approach is designed to efficiently handle up to 10,000 pings, with the space complexity being proportional to the number of pings within the time window.

How does GhostInterview help with solving the Number of Recent Calls problem?

GhostInterview provides a structured approach to solving the problem, helping you understand the queue-driven state processing and avoid common mistakes in time and space management.

What is the primary pattern for solving the Number of Recent Calls problem?

The primary pattern involves queue-driven state processing, where a queue is used to efficiently track and count recent requests within the time window.

#933

Easy

auto_awesome队列·driven·状态·processing

LeetCode 题解工作台

最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。请你实现 RecentCounter 类： RecentCounter() 初始化计数器，请求数为 0 。 int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 …

设计队列数据流

题目描述

写一个 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⁴ 次

lightbulb

解题思路

方法一：队列

由题得知，t 是严格递增的，当一个元素不满足 [t - 3000, t] 条件时，在后续的请求当中，它也不可能满足。

对此，需要将其从记录容器中移除，减少无意义的比较。

可以使用队列。每次将 t 进入队尾，同时从队头开始，依次移除小于 t - 3000 的元素。然后返回队列的大小（q.size()）即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class RecentCounter:
    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)


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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate understands how to implement a queue-driven solution for managing time-based state.
question_mark
The candidate focuses on time and space optimization by leveraging a queue.
question_mark
The candidate demonstrates efficiency in handling large numbers of requests within a given time frame.

warning

常见陷阱

外企场景

error
Not handling edge cases where the time window is close to or exceeds 3000 milliseconds.
error
Failing to manage the queue size and removing outdated pings, leading to incorrect results.
error
Not considering the time complexity of the solution and implementing a brute force method that cannot handle large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider handling requests for different time windows (e.g., 1000ms or 5000ms).
arrow_right_alt
Implement a version where the queue size is limited to a fixed number of pings.
arrow_right_alt
Introduce a new requirement where pings need to be categorized or processed differently based on time of arrival.

help

常见问题

外企场景

继续练习

#1670 设计前中后队列 #1825 求出 MK 平均值 #901 股票价格跨度