算法隊列之最近請求次數

題目：

寫一個 RecentCounter 類來計算特定時間範圍内最近的請求。

請你實作 RecentCounter 類：

RecentCounter() 初始化計數器，請求數為 0 。

int ping(int t) 在時間 t 添加一個新請求，其中 t 表示以毫秒為機關的某個時間，并傳回過去 3000 毫秒内發生的所有請求數（包括新請求）。确切地說，傳回在 [t-3000, t] 内發生的請求數。

保證 每次對 ping 的調用都使用比之前更大的 t 值。

輸入：
["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      

解決思路

題目意思就是往隊列裡存放元素啊，每次ping就存一個數，然後存的時候看一下之前的數是否在t-3000之外了，是就删除；

比如題目給的例子：

輸入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
輸出：
[null, 1, 2, 3, 3]
就是第一次存個1，第二次存個100……

然後每次存的時候，看看之前存的元素，有多少個在這次存的 t 到t-3000之間；

存1的時候，1在[-2999,1]之間，就這一個數，是以說傳回數目1；
……

存3002的時候就删除1，因為1不在[2,3002]之間，而100，3001，3002都是在[2,3002]之間，就傳回數目3；      

代碼實作

class RecentCounter {
    Queue<Integer> q;
    public RecentCounter() {
        q = new LinkedList();
    }

    public int ping(int t) {
        q.add(t);
        while (q.peek() < t - 3000) {
            q.poll();
        }
        return q.size();
    }
}      

最後

• 時間複雜度：O(Q)，其中 QQ 是 ping 的次數。
• 空間複雜度：O(W)，其中 W = 3000 是隊列中最多存儲的 ping 的記錄數目。

• ​​# UE4：來為我們的角色制作一個血條吧​​
• ​​使用 Google Breakpad 來助力解決程式崩潰​​
• ​​UE4 多人遊戲伺服器探索​​
• ​​使用虛幻引擎自動化工具實作自動化部署​​
• ​​如何在 UE4 中制作一扇自動開啟的大門​​
• ​​如何在 UE4 中用代碼去控制角色移動​​
• ​​如何給 UE4 場景添加遊戲角色​​
• ​​UE4：Android 平台開發實踐指南​​
• ​​UE4 開發避坑指南（持續更新）​​
• ​​新年開工啦，放個小煙花慶祝一下​​
• ​​聊聊與蘋果稽核員的愛恨情仇(下)​​
• ​​聊聊與蘋果稽核員的愛恨情仇(上)​​
• ​​一名普通工具人的 2021 | 2021年終總結​​
• ​​二叉樹刷題總結：二叉搜尋樹的屬性​​
• ​​二叉樹總結：二叉樹的屬性​​
• ​​二叉樹總結：二叉樹的修改與構造​​
• ​​StoreKit2 有這麼香？嗯，我試過了，真香​​
• ​​看完這篇文章，再也不怕面試官問我如何構造二叉樹啦！​​
• ​​那幫做遊戲的又想讓大家氪金，太壞了！​​
• ​​手把手帶你撸一個網易雲音樂首頁 | 适配篇​​
• ​​手把手帶你撸一個網易雲音樂首頁（三）​​
• ​​手把手帶你撸一個網易雲音樂首頁（二）​​
• ​​手把手帶你撸一個網易雲音樂首頁（一）​​
• ​​代碼要寫注釋嗎？寫你就輸了​​
• ​​Codable釋出這麼久我就不學，摸魚爽歪歪，哎~就是玩兒​​
• ​​iOS 優雅的處理網絡資料，你真的會嗎？不如看看這篇​​
• ​​UICollectionView 自定義布局！看這篇就夠了​​

1. 關注公衆号--- HelloWorld傑少