題目難度: 簡單
原題鏈接
今天繼續(xù)更新 Leetcode 的劍指 Offer（專項(xiàng)突擊版）系列, 大家在公眾號 算法精選 里回復(fù)
劍指offer2就能看到該系列當(dāng)前連載的所有文章了, 記得關(guān)注哦~
題目描述
寫一個(gè) RecentCounter 類來計(jì)算特定時(shí)間范圍內(nèi)最近的請求。
請實(shí)現(xiàn) RecentCounter 類：
- RecentCounter() 初始化計(jì)數(shù)器，請求數(shù)為 0 。
- int ping(int t) 在時(shí)間 t 添加一個(gè)新請求，其中 t 表示以毫秒為單位的某個(gè)時(shí)間，并返回過去 3000 毫秒內(nèi)發(fā)生的所有請求數(shù)（包括新請求）。確切地說，返回在 [t-3000, t] 內(nèi)發(fā)生的請求數(shù)。
保證 每次對 ping 的調(diào)用都使用比之前更大的 t 值。
示例：
- 輸入：
- inputs = [“RecentCounter”, “ping”, “ping”, “ping”, “ping”]
- inputs = [[], [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^9
- 保證每次對 ping 調(diào)用所使用的 t 值都 嚴(yán)格遞增
- 至多調(diào)用 ping 方法 10^4 次
題目思考
- 可以使用什么數(shù)據(jù)結(jié)構(gòu)模擬整個(gè)過程?
解決方案
思路
- 分析題目, 要想動(dòng)態(tài)維護(hù)過去 3000 毫秒內(nèi)發(fā)生的所有請求數(shù), 需要支持一端添加新元素, 另一端移除老元素, 顯然可以使用雙端隊(duì)列來模擬這個(gè)過程
- 每次調(diào)用 ping 函數(shù)時(shí):
- 先將新請求添加到隊(duì)列末尾
- 然后循環(huán)判斷隊(duì)列開頭請求是否不在時(shí)間窗口內(nèi), 不在的話移除它并繼續(xù)循環(huán)
- 循環(huán)結(jié)束時(shí), 隊(duì)列里存儲的就是時(shí)間窗口內(nèi)的所有請求, 返回隊(duì)列長度即可
- 下面的代碼就對應(yīng)了上面的整個(gè)過程, 并且有詳細(xì)的注釋, 方便大家理解
復(fù)雜度
- 時(shí)間復(fù)雜度 O(1): 每個(gè)請求最多入隊(duì)和出隊(duì)各一次, 所以每次操作的均攤時(shí)間復(fù)雜度為 O(1)
- 空間復(fù)雜度 O(N): 雙端隊(duì)列最多存儲全部 N 個(gè)元素
代碼
class RecentCounter:
def __init__(self):
# 初始化一個(gè)雙端隊(duì)列
self.q = collections.deque()
def ping(self, t: int) -> int:
# 將當(dāng)前元素加入隊(duì)尾
self.q.append(t)
# 這里由于剛?cè)腙?duì)一個(gè)元素, 且其一定不滿足循環(huán)條件
# 所以可以保證隊(duì)列至少有一個(gè)元素(t), 無需判斷q是否為空
while self.q[0] < t - 3000:
# 隊(duì)頭元素不在時(shí)間窗口[t-3000,t]內(nèi)了, 將其出隊(duì)
self.q.popleft()
# 最終隊(duì)列剩余的元素個(gè)數(shù)即為時(shí)間窗口內(nèi)的總請求數(shù)
return len(self.q)
大家可以在下面這些地方找到我~??
我的 GitHub
我的 Leetcode
我的 CSDN
我的知乎專欄
我的頭條號
我的牛客網(wǎng)博客
我的公眾號: 算法精選, 歡迎大家掃碼關(guān)注~??文章來源：http://www.zghlxwxcb.cn/news/detail-690466.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-690466.html
到了這里，關(guān)于Leetcode 劍指 Offer II 042. 最近的請求次數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
