Number of Recent Calls

題目描述

實作 RecentCounter 類別，有一個 ping(t) 方法，t 代表某次請求的時間（毫秒）。回傳在 [t - 3000, t] 時間範圍內的請求數量（包含當前請求）。

輸入: ["RecentCounter", "ping", "ping", "ping", "ping"]
      [[], [1], [100], [3001], [3002]]
輸出: [null, 1, 2, 3, 3]

解釋: ping(3002) 時，時間範圍 [2, 3002]，
      時間 1 已超出範圍，所以只有 100, 3001, 3002 共 3 個。

解題思路

接收 ping(t)

呼叫 queue.Enqueue(t) 將時間戳加入 Queue 尾端

移除過期請求

用 while 迴圈檢查 Queue 前端，若 queue.Peek() 小於 t - 3000 就 Dequeue 移除

回傳數量

Queue.Count 就是時間窗口 [t-3000, t] 內的請求數

程式碼

C#

csharp

public class RecentCounter {
    private Queue<int> queue;
 
    public RecentCounter() {
        queue = new Queue<int>();
    }
 
    public int Ping(int t) {
        queue.Enqueue(t); // 加入新請求
        // 移除超出時間窗口的舊請求
        while (queue.Peek() < t - 3000) {
            queue.Dequeue();
        }
        return queue.Count;
    }
}

TypeScript

typescript

class RecentCounter {
    private queue: number[];
 
    constructor() {
        this.queue = [];
    }
 
    ping(t: number): number {
        this.queue.push(t); // 加入新請求
        // 移除超出時間窗口的舊請求
        while (this.queue[0] < t - 3000) {
            this.queue.shift();
        }
        return this.queue.length;
    }
}

Python

python

from collections import deque
 
class RecentCounter:
    def __init__(self):
        self.queue = deque()
 
    def ping(self, t: int) -> int:
        self.queue.append(t)  # 加入新請求
        # 移除超出時間窗口的舊請求
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(1) 攤銷 | O(W) |

W 是時間窗口大小（最多 3000ms 內的請求數）。Time 為 O(1) 攤銷，因為每個元素最多入隊出隊各一次，雖然單次 ping 可能移除多個過期元素，但分攤到所有操作後每個元素只被處理兩次。Space 為 O(W) 是因為 Queue 最多同時存放時間窗口內的所有請求。

邊界情況

第一次 ping：Queue 為空直接加入，不會進入 while 移除迴圈，回傳 1
所有 ping 時間間隔都在 3000ms 內：不會有任何元素被移除，Queue 持續增長
連續大量密集 ping 後很久才來一次：單次 ping 可能一次移除大量過期元素，但攤銷仍為 O(1)

圖解

Queue: [1]

ping(100)→

Queue: [1, 100]

ping(3001)→

Queue: [1, 100, 3001]

ping(3002), 移除 1→

Queue: [100, 3001, 3002]

圖表展示了 Queue 的狀態隨每次 ping 的變化。關鍵步驟在 ping(3002) 時：時間窗口變為 [2, 3002]，Queue 前端的 1 小於 2 被移除，最終 Queue 剩 3 個元素即為答案。

進階觀點

💡面試追問

Q: 為什麼用 Queue 而不是 Array？ A: Queue 的 FIFO 特性天然適合時間窗口問題 — 請求按時間遞增加入，過期的一定在前端，只需從前端移除。Array 也能做但語意不如 Queue 清晰。

Q: TypeScript 的 Array.shift() 效能問題如何解決？ A: Array.shift() 是 O(n) 因為要移動後續所有元素。生產環境可改用 linked list 實現真正的 O(1) dequeue，或用 circular buffer。Python 的 deque.popleft() 底層是雙向鏈結串列，已經是 O(1)。

Q: 如果要支援任意時間窗口大小怎麼做？ A: 把 3000 改為建構子參數即可，邏輯完全不變。也可以用 Binary Search（bisect_left）在排序的 list 中找到窗口左邊界，但 Queue 方案更簡潔。

變體：滑動窗口中位數、滑動窗口最大值（LC 239）。

理解測驗

🤔 為什麼 Queue 適合解這題？

🤔 ping(3002) 時，為什麼要移除時間為 1 的請求？