敲击计数器
难度:
标签:
题目描述
代码结果
运行时间: 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)而非其他数据结构,如列表或链表,来存储时间戳?
▷🦆
在`getHits`方法中,如果所有时间戳都在5分钟以内,该方法的时间复杂度是多少?
▷🦆
当`hit`方法在短时间内被频繁调用时,队列的长度可能会怎样变化,这对内存使用有何影响?
▷