933. 最近的請(qǐng)求次數(shù)

寫一個(gè) RecentCounter 類來(lái)計(jì)算最近的請(qǐng)求。

它只有一個(gè)方法：ping(int t)，其中 t 代表以毫秒為單位的某個(gè)時(shí)間。

返回從 3000 毫秒前到現(xiàn)在的 ping 數(shù)。

任何處于 [t - 3000, t] 時(shí)間范圍之內(nèi)的 ping 都將會(huì)被計(jì)算在內(nèi)，包括當(dāng)前（指 t 時(shí)刻）的 ping。

保證每次對(duì) ping 的調(diào)用都使用比之前更大的 t 值。

示例:

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

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-recent-calls/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

• 入隊(duì)法

思路：題目問(wèn)題相當(dāng)于：從第一次 ping開始到3000ms之后總共的ping的次數(shù)，也就是說(shuō)要篩選：當(dāng)前ping curPing - 第一次ping firstPing <= 3000 的ping

1. 可以使用隊(duì)列完成，將每次的ping都存入隊(duì)列中
2. 每次判斷當(dāng)前 ping 是否符合題意，如果不滿足，則出隊(duì)隊(duì)首元素
3. 返回隊(duì)列大小即可

private Queue<Integer> queue;

    public RecentCounter() {
        queue = new LinkedList<>();
    }
    public int ping(int t) {
        queue.add(t);
        while ((t - 3000) > queue.peek()) queue.poll();
        return queue.size();
    }

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n), n表示ping的次數(shù)
• 空間復(fù)雜度：O(n), n表示隊(duì)列的空間大小，也就是滿足條件的ping數(shù)

• 源碼

• 我會(huì)每天更新新的算法，并盡可能嘗試不同解法，如果發(fā)現(xiàn)問(wèn)題請(qǐng)指正

• Github