LeetCode 362. 敲击计数器

Categories:

题目描述
思路分析
1. 解法一：队列压缩计数（推荐）
相似题目

题目描述

✅ 362. 敲击计数器

思路分析

解法一：队列压缩计数（推荐）

核心思路：

用队列保存最近 5 分钟内的时间戳与计数对 (timestamp, count)。

hit 时若与队尾时间戳相同则累加，否则新入队。

getHits 时弹出过期元素并累计剩余计数。

复杂度分析：

时间复杂度：O(1) 均摊，每个元素最多入队出队一次。

空间复杂度：O(k)，其中 k 为 5 分钟窗口内的不同时间戳数量。

import java.util.ArrayDeque;
import java.util.Deque;

class HitCounter {
    private final Deque<int[]> queue = new ArrayDeque<>();
    private int total = 0;

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

        total++;
    }

    public int getHits(int timestamp) {
        // 清理过期时间戳
        while (!queue.isEmpty() && timestamp - queue.peekFirst()[0] >= 300) {
            total -= queue.pollFirst()[1];
        }

        return total;
    }
}

type HitCounter struct {
	times []hitPair
	head  int
	total int
}

type hitPair struct {
	time  int
	count int
}

func Constructor() HitCounter {
	return HitCounter{}
}

func (h *HitCounter) Hit(timestamp int) {
	if len(h.times) > h.head && 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 {
	// 清理过期时间戳
	for h.head < len(h.times) && timestamp-h.times[h.head].time >= 300 {
		h.total -= h.times[h.head].count
		h.head++
	}

	return h.total
}

相似题目

题目	难度	考察点
353. 贪吃蛇	中等	队列 + 设计
359. 日志速率限制器	简单	数据流
622. 设计循环队列	中等	队列
641. 设计循环双端队列	中等	双端队列
1472. 设计浏览器历史记录	中等	数据结构设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/69521907