leetcode
leetcode 301 ~ 350
敲击计数器

敲击计数器

难度:

标签:

题目描述

代码结果

运行时间: 27 ms, 内存: 0.0 MB


/*
 * 思路:
 * 1. 创建一个类 HitCounter,其中包含一个List来存储敲击的时间戳。
 * 2. 实现hit(int timestamp)方法来记录敲击事件。
 * 3. 实现getHits(int timestamp)方法来返回过去5分钟内的敲击次数。
 * 4. 使用Java Stream API简化getHits方法。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
 
public class HitCounter {
    private List<Integer> hits;
 
    public HitCounter() {
        hits = new ArrayList<>();
    }
 
    public void hit(int timestamp) {
        hits.add(timestamp);
    }
 
    public int getHits(int timestamp) {
        int start = timestamp - 300;
        return (int) hits.stream()
                         .filter(time -> time > start)
                         .count();
    }
 
    public static void main(String[] args) {
        HitCounter counter = new HitCounter();
        counter.hit(1);
        counter.hit(2);
        counter.hit(3);
        System.out.println(counter.getHits(4)); // 输出 3
        counter.hit(300);
        System.out.println(counter.getHits(300)); // 输出 4
        System.out.println(counter.getHits(301)); // 输出 3
    }
}
 

解释

方法:

该题解的整体思路是利用一个双向队列 (deque) 存储每次敲击的时间戳。当调用 hit 方法时,时间戳被添加到 deque 的尾部。当调用 getHits 方法时,该方法首先移除 deque 中所有超过 5 分钟之前的时间戳,然后返回 deque 中剩余的时间戳数量,即为最近 5 分钟内的敲击次数。

时间复杂度:

O(1)

空间复杂度:

O(300) 或 O(1),视时间窗口大小为固定值时可认为是常数空间。

代码细节讲解

🦆
为什么选择使用双向队列(deque)而非其他数据结构,如列表或链表,来存储时间戳?
双向队列(deque)被选择用于存储时间戳主要是因为其在前端和后端操作的高效性。在这个问题中,我们需要频繁地在队列的尾部添加新的时间戳(hit操作),同时也需要从队列的头部移除过期的时间戳(getHits操作)。使用列表(如Python中的list)进行这样的操作会非常低效,因为列表的头部插入或删除操作需要O(n)时间复杂度,其中n是列表的长度。而链表虽然可以在O(1)时间复杂度内完成这些操作,但其在实际的内存结构中不如deque连续,可能导致更高的缓存未命中率和额外的内存开销。双向队列结构可以在两端进行O(1)时间复杂度的插入和删除操作,非常适合本问题的需求。
🦆
在`getHits`方法中,如果所有时间戳都在5分钟以内,该方法的时间复杂度是多少?
如果在`getHits`方法调用时,双向队列内的所有时间戳都还在5分钟以内,则不会执行任何的移除操作,此时该方法主要执行的是返回队列长度的操作,这是一个O(1)时间复杂度的操作。因此,在所有时间戳都在5分钟以内的情况下,`getHits`方法的时间复杂度为O(1)。
🦆
当`hit`方法在短时间内被频繁调用时,队列的长度可能会怎样变化,这对内存使用有何影响?
当`hit`方法在短时间内被频繁调用时,每次调用都会向双向队列的尾部添加一个新的时间戳,导致队列的长度增加。如果这些`hit`操作发生在极短的时间间隔内,队列的长度可能会迅速增长,从而占用更多的内存资源。尤其是在高流量的应用场景下,队列可能会暂时存储大量的时间戳,直到这些时间戳超过5分钟后才开始逐渐被移除。这种情况下,内存的使用会随着队列长度的增加而增加,可能导致内存压力或在极端情况下导致内存溢出,特别是当系统内存有限时更需注意这一点。因此,正确管理和监控内存使用,以及合理设定时间戳的存储策略,对于维持系统稳定性和性能是非常关键的。

相关问题

日志速率限制器

日志速率限制器