付費限定文章

系統設計: 最近幾筆的來電紀錄_Leetcode 精選75題解析

Julian Hochgesang on Unsplash

題目敘述

題目會給我們一個定義好的類別和function介面，要求我們實作建構子和ping() function來滿足指定的需求。

RecentCounter類別的建構子

建構子應該初始化來電紀錄，內容為空(零筆資料)

int ping(int t)

t代表來電時刻，單位是毫秒millisecond。

ping() function 應該維護[t-3000, t]區間內的來電紀錄，並且返回總共有幾筆來電落在[t-3000, t]這個區間內。

題目還保證每一次呼叫, t值會逐漸遞增。

題目的原文敘述

測試範例

Example 1:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

約束條件

Constraints:

• 1 <= t <= 10^9

t值介於1~10^9之間。

• Each test case will call ping with strictly increasing values of t.

每次呼叫ping()時，t值會逐漸遞增。

• At most 10^4 calls will be made to ping.

動態測試時，最多有10^4次 ping() function呼叫。

演算法

題目給了一個很強的條件，每次呼叫ping()時，t值會逐漸遞增。

另一方面，又要求維護[t-3000, t]區間內的來電紀錄，並且返回總共有幾筆來電落在[t-3000, t]這個區間內。