LeetCode 362. 敲击计数器

2020-12-11 HGNULB 约 7 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 362. 敲击计数器

题意分析

要设计一个计数器，支持两种带时间戳的调用：hit(timestamp) 记录一次敲击，getHits(timestamp) 返回过去 $5$ 分钟（即 $300$ 秒）内的敲击总数。时间戳以秒为单位。

「过去 $5$ 分钟」的区间是左开右闭还是闭区间，直接决定边界写法。按题目定义，在时刻 $t$ 查询，统计的是时间戳落在 $(t-300,\ t]$ 内的敲击，也就是恰好 $300$ 秒之前的那些敲击已经过期。

最关键的约束是「所有调用的 timestamp 单调不减」。这条保证意味着时间只会前进，早过期的敲击一旦过期就永远过期，不会再回来——这正是可以用一个只进不退的队列来管理数据的前提。

另一个信号是同一秒内可能发生大量敲击。若每次敲击都单独存一条记录，内存和遍历代价都与敲击总次数成正比；而窗口内的不同时间戳最多只有 $300$ 个，把同一秒合并成一条记录能把规模压到常数级。

边界方面：查询时窗口内没有任何敲击应返回 $0$；查询本身可能在两次敲击之间被多次调用，重复清理必须幂等；同一时间戳上先 hit 再 getHits，那次敲击应当被计入。

解法：队列压缩计数

核心思路

最朴素的实现是把每次敲击的时间戳原样存进一个列表，查询时从后往前扫，累计所有大于 $t-300$ 的记录。这在功能上没错，但每次查询的代价与窗口内敲击次数成正比，而题目明确提示「每秒可能有很多次敲击」，这个次数没有上界。

瓶颈有两层。第一层是过期数据一直堆在容器里，查询时反复被跳过；第二层是同一秒的敲击被拆成很多条，白白放大了数据量。

针对第一层，利用时间戳单调不减这个性质：过期是单向的，一旦某条记录过期，它前面的记录也全都过期，之后也永远不会复活。因此每次 hit 或 getHits 都先从队首持续弹出过期项。每条记录一生只入队一次、出队一次，清理代价被均摊成常数。

针对第二层，把队列元素从「单次敲击」升级成「时间戳 + 该秒的敲击数」的二元组。由于时间戳单调不减，同一秒的敲击必然连续到达，只需检查队尾时间戳是否与当前相同，相同就把计数加一，否则追加新节点。这样队列长度不超过窗口内不同时间戳的个数，也就是 $300$。

再维护一个 total 表示队列中所有计数之和，就不必在查询时遍历求和。整个结构的不变量是：队列中的记录时间戳严格递增、全部落在最近一次清理所用的窗口内，且 total 恒等于队列中各计数之和。hit 时二者同步增加，清理时二者同步减少。

解题步骤

结构里放一个双端队列存二元组，外加一个整型 total。用队列而非普通数组，是因为需要队首删除与队尾追加两种 $O(1)$ 操作。

每次操作先调用同一个清理逻辑，删除所有满足 timestamp - 队首时间戳 >= 300 的节点，并同步从 total 中减去它们的计数。hit 也要清理，才能让长期只有写入、没有查询时的空间仍受窗口大小约束。

hit(timestamp) 清理后，看队列非空且队尾时间戳是否等于 timestamp。相等就把队尾的计数加一，这一步是压缩的核心，让同一秒内的任意多次敲击只占一个节点。

若不相等（或队列为空），追加一个计数为 $1$ 的新节点。因为时间戳单调不减，新时间戳必然大于队尾，追加后队列仍保持递增。

无论走哪个分支，都把 total 加一，保持「total 等于队列计数之和」这条不变量。

getHits(timestamp) 时先做清理：只要队列非空且 timestamp - 队首时间戳 >= 300，就把队首弹出并从 total 里减去它的计数。用大于等于而非大于，是因为恰好相差 $300$ 秒的敲击已经不在窗口内。

清理是循环而非单次判断，因为两次查询之间可能过去很久，一次要清掉多个节点；但由于每个节点只会被清理一次，多轮循环的总代价仍是均摊常数。

清理完毕后直接返回 total，无需再遍历队列求和。

以 hit(1)、hit(2)、hit(3)、getHits(4)、hit(300)、getHits(300)、getHits(301) 走一遍：hit(1) 时队列为空，追加节点 $(1,1)$，total 变为 $1$。hit(2) 时队尾时间戳 $1$ 不等于 $2$，追加 $(2,1)$，total 变为 $2$。hit(3) 同理追加 $(3,1)$，total 变为 $3$，队列是 $(1,1),(2,1),(3,1)$。getHits(4) 先清理：队首时间戳 $1$，$4-1=3$ 小于 $300$，不过期，循环立即结束，返回 total 即 $3$。hit(300) 时队尾时间戳 $3$ 不等于 $300$，追加 $(300,1)$，total 变为 $4$。getHits(300) 清理时队首 $1$ 满足 $300-1=299 < 300$，仍在窗口内，返回 $4$——注意此刻同一秒的那次敲击也算数。getHits(301) 清理时队首 $1$ 满足 $301-1=300 \ge 300$，弹出并把 total 减为 $3$；再看新队首 $2$，$301-2=299 < 300$，停止清理，返回 $3$。三次查询的结果依次是 $3$、$4$、$3$，与预期一致。

代码实现

// hit 时若与队尾时间戳相同则累加，否则新入队。
class HitCounter {
    private final Deque<int[]> queue = new ArrayDeque<>();
    private int total = 0;

    public void hit(int timestamp) {
        evictExpired(timestamp);

        if (!queue.isEmpty() && queue.peekLast()[0] == timestamp) {
            queue.peekLast()[1]++;
        } else {
            queue.addLast(new int[]{timestamp, 1});
        }

        total++;
    }

    public int getHits(int timestamp) {
        evictExpired(timestamp);
        return total;
    }

    private void evictExpired(int timestamp) {
        while (!queue.isEmpty() && timestamp - queue.peekFirst()[0] >= 300) {
            total -= queue.pollFirst()[1];
        }
    }
}

// hit 时若与队尾时间戳相同则累加，否则新入队。
type HitCounter struct {
    times []hitPair
    total int
}

type hitPair struct {
    time  int
    count int
}

func Constructor() HitCounter {
    return HitCounter{}
}

func (h *HitCounter) Hit(timestamp int) {
    h.evictExpired(timestamp)

    if len(h.times) > 0 && h.times[len(h.times)-1].time == timestamp {
        h.times[len(h.times)-1].count++
    } else {
        h.times = append(h.times, hitPair{time: timestamp, count: 1})
    }

    h.total++
}

func (h *HitCounter) GetHits(timestamp int) int {
    h.evictExpired(timestamp)
    return h.total
}

func (h *HitCounter) evictExpired(timestamp int) {
    for len(h.times) > 0 && timestamp-h.times[0].time >= 300 {
        h.total -= h.times[0].count
        h.times = h.times[1:]
    }
}

复杂度分析

时间复杂度：单次 hit 或 getHits 最坏会清理 $k$ 个过期时间组，是 $O(k)$；但每个时间组只入队、出队各一次，因此一串操作的均摊时间为 $O(1)$。由于队列始终只保留 300 秒窗口内的时间组，这里的 $k$ 也不超过 300。

空间复杂度：$O(w)$，其中 $w$ 是当前 300 秒窗口内不同时间戳的数量；同一秒的多次敲击被压缩到一个节点。最坏情况下 $w = 300$（时间戳以秒为单位且单调递增）。

关键点总结

队列节点保存 (timestamp, count)，total 始终等于所有队列节点计数之和；这两个状态共同让查询无需再次求和。

hit 利用时间戳单调不减的保证，只比较队尾就能完成同秒压缩。

hit 和 getHits 都从队首清理 timestamp <= 当前时间 - 300 的节点；边界判断来自窗口 (timestamp - 300, timestamp]。

若面试官追问“调用量极大怎么办”，可以说明按秒聚合后队列最多 300 个节点；也可以直接使用长度 300 的环形数组保存时间戳与计数。

易错点总结

过期条件写成 timestamp - front > 300：恰好相差 300 秒的记录也已经不在窗口中。比如在 1 秒敲击，301 秒查询时必须删除它，条件应使用 >= 300。

每次只弹出一个过期节点：两次查询间隔很久时可能有多个时间组同时过期，必须用 while 持续清理。

弹队首却不从 total 中减去计数：队列内容正确但返回值会永久偏大；修改队列和聚合值必须是一个原子语义动作。

同一时间戳仍逐次入队：答案虽可能正确，却失去按秒压缩的空间上界；连续百万次 hit(100) 应只产生一个 (100, 1000000) 节点。

相似题目

题目	难度	与本题的联系
933. 最近的请求次数	简单	同样清理时间窗口队首，但每个时间戳只有一次请求
346. 数据流中的移动平均值	简单	固定元素个数的队列窗口，需要额外维护窗口总和
359. 日志速率限制器	简单	按消息维护时间窗口，考察哈希表中的过期状态