933. Number of Recent Calls

📘 題目敘述

你有一個 RecentCounter 類別，用來計算在某個時間範圍內「最近的請求數量」。

請你實作 RecentCounter 類別：

• RecentCounter()：用 0 個最近請求初始化計數器。
• int ping(int t)：在時間 t 新增一個請求，其中 t 代表某個時間點（毫秒），並回傳在過去 3000 毫秒內（包含這個新請求）發生的請求數量。更精確地說，回傳在區間 [t - 3000, t]（包含兩端）內發生的請求數量。

題目保證：每次呼叫 ping 時使用的 t 都會嚴格大於前一次呼叫的 t。

條件限制

• 1 <= t <= 10^9
• 每個測資會用嚴格遞增的 t 呼叫 ping
• 每個測資最多呼叫 ping 10^4 次

🧠 解題思路

我把這題當成一個固定長度的「滑動時間窗」：

• 我只在乎最近 3000 毫秒內的呼叫時間點。
• 因為 t 嚴格遞增，所以所有呼叫時間會「越來越大」地進來。
• 這種「新的時間一直加入、舊的時間一直過期」的結構，最適合用 queue（FIFO）：

• 新的 t 從尾端 push
• 太舊的時間（小於 t-3000）會從前端 pop

核心不變式：queue 裡永遠只留著落在 [t-3000, t] 的所有呼叫時間。

所以 queue 的大小就是答案。

所有變數

• calls：queue<int>，存目前「還在 3000ms 視窗內」的所有呼叫時間（由小到大）

🪜 主要流程步驟

1. 先把本次呼叫時間放進 queue

• calls.push(t)
• 代表：這次 ping 一定要被計入 [t-3000, t]。

2. 把過期的時間從 queue 前端丟掉

• 只要 calls.front() < t - 3000 就 pop()
• 因為 front() 是目前最早的呼叫時間，如果它都過期了，那它前面也不可能還有有效的（queue 只會更舊）

做完這段後，queue 裡就只剩下合法區間內的呼叫。

3. 回傳 queue 目前大小

• return calls.size();
• 因為這就是區間 [t-3000, t] 的呼叫次數。

💻 程式碼實作

class RecentCounter {
public:
    queue<int> calls;
    RecentCounter() {
        
    }

    int ping(int t) {
        calls.push(t);
        while (calls.front() < t - 3000) {
            calls.pop();
        }
        return calls.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

🔗 題目連結

https://leetcode.com/problems/number-of-recent-calls/