LeetCode 362. 敲击计数器

约 4 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 会员题 2-5 微软
标签
数组 二分查找 设计 队列 数据流

题目描述

✅ 362. 敲击计数器

题意分析

hit(timestamp) 记录一次敲击，getHits(timestamp) 返回最近五分钟的敲击总数。查询时刻为 t 时，只保留满足 t - 300 < timestamp <= t 的记录；所有调用的时间戳单调不减，同一秒允许有多次敲击。

解法：队列压缩计数

核心思路

[!blue]

时间只会向前推进，旧记录是否过期只由它的时间戳决定，适合用按时间排列的队列维护。过期记录一定集中在队首，而且一旦过期就不会重新有效，可以永久移除。

如果每次敲击都存一条记录，同一秒的密集请求会占用很多空间。它们会在同一时刻过期，可以合并成 (时间戳, 次数)：时间与队尾相同就增加队尾次数，否则追加一组。时间戳单调不减，保证需要合并的组只能位于队尾。

另外维护 total，始终等于队列中各组次数之和。写入时加一，移除过期组时扣掉整组次数。查询只需先清理，再返回 total，不必重新遍历队列求和。

两种操作都先清理，避免长时间只有写入、没有查询时积累历史组。清理条件是 当前时间 - 队首时间 >= 300，并且要循环移除，直到队首有效或队列为空；此时后面的时间更新，也都处于有效窗口内。

解题步骤

  1. 用空队列和 total = 0 初始化计数器。
  2. 每次调用先移除全部相差至少 300 秒的队首组，并同步减少 total。
  3. 对 hit，合并同秒队尾或追加新组，再令 total 加一。
  4. 对 getHits，直接返回清理后的 total；队列为空时自然返回 0。

代码实现

// 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:]
    }
}

复杂度分析

  • 时间复杂度：一次调用最坏清理 $O(W)$ 个组，W = 300 为窗口秒数。每个时间组只入队、出队一次，所以整个调用序列中，每次操作均摊 $O(1)$。
  • 空间复杂度：$O(W)$，整数秒窗口最多三百个时间组。

关键点总结

[!green]

  • 同一秒次数与组数量分开，密集敲击不增加相同时间组。
  • 队列按时间有序，只需从队首清理，就能保留完整有效窗口。
  • 队列变化时同步维护 total，查询无需再次求和。
  • 写入也清理，空间才只与窗口秒数有关。

易错点总结

[!yellow]

  • 过期条件用严格大于三百，会多保留边界敲击。
  • 只删队首一次，可能残留其他过期组。
  • 移除队列组却不扣总数，会返回过大的累计值。
  • 不能用队列长度当答案，一组可能代表同一秒的多次敲击。

相似题目

题目 难度 关联与区别
933. 最近的请求次数 简单 同样删除时间窗口外的请求，原题时间戳严格递增且窗口为3000毫秒，本题按秒统计命中。
346. 数据流中的移动平均值 简单 同样维护最近窗口，本题窗口按时间限定，移动平均题按元素个数限定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2020/69521907
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！