教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」中 0362. 敲击计数器 的完整技术解析围绕统计过去 5 分钟300 秒内敲击次数这一经典数据流计数问题讲解基于队列的滑动窗口实现并结合仓库中队列源码剖析其底层原理。读完本文你将掌握队列在时间窗口统计场景下的建模方法理解hit与getHits两个操作的时间复杂度来源并能够应对每秒敲击次数很大的进阶优化思路。题目概述题目0362. 敲击计数器Design Hit Counter标签设计、队列、数组、二分查找、数据流难度中等题目链接见 docs/solutions/0300-0399/index.md 中 0362 条目题目要求设计一个敲击计数器HitCounter使其能够统计在过去5 分钟即过去300 秒内发生的敲击次数。系统接受一个以秒为单位的时间戳参数timestamp并且可以假定所有调用按时间顺序进行即timestamp单调递增几次敲击可能同时发生。需要实现HitCounter类方法说明HitCounter()初始化命中计数器系统void hit(int timestamp)记录在timestamp单位秒发生的一次命中同一个timestamp中可能出现多次点击int getHits(int timestamp)返回timestamp在过去 5 分钟内即过去 300 秒的命中次数约束说明1 timestamp 2 * 10^9所有对系统的调用都是按时间顺序进行的timestamp单调递增hit和getHits最多被调用 300 次进阶如果每秒的敲击次数是一个很大的数字计数器还能应对吗示例演示输入 [HitCounter, hit, hit, hit, getHits, hit, getHits, getHits] [[], [1], [2], [3], [4], [300], [300], [301]] 输出 [null, null, null, null, 3, null, 4, 3]解释HitCounter counter new HitCounter(); counter.hit(1); // 在时刻 1 敲击一次 counter.hit(2); // 在时刻 2 敲击一次 counter.hit(3); // 在时刻 3 敲击一次 counter.getHits(4); // 在时刻 4 统计过去 5 分钟内的敲击次数返回 3 counter.hit(300); // 在时刻 300 敲击一次 counter.getHits(300);// 在时刻 300 统计过去 5 分钟内的敲击次数返回 4 counter.getHits(301);// 在时刻 301 统计过去 5 分钟内的敲击次数返回 3注意最后一次调用在时刻 301 时时刻 1 已经超出 300 秒窗口301 - 300 1窗口要求严格大于 1因此命中的是时刻 2、3、300 三次返回 3。解题思路 1基于队列的滑动窗口核心建模窗口统计问题的本质是维护一段长度为 300 秒的时间区间内的数据。由于调用时间戳单调递增所有命中事件天然构成一个按时间排序的序列这与队列「先进先出FIFO」的特性完全吻合最先发生的命中最早过期应当最先被移除队头出队最新发生的命中在窗口内存活时间最长应当最后被移除队尾入队。因此可以用一个队列存储所有敲击时间戳队列中的元素天然按时间戳升序排列。具体步骤初始化创建一个空队列queue用于存储时间戳hit 操作将当前时间戳timestamp加入队列队尾入队getHits 操作计算时间窗口的起始时间start_time timestamp - 300移除队列中所有小于等于start_time的时间戳过期命中队头出队返回队列中剩余元素的个数即为过去 300 秒内的命中次数。参考代码from collections import deque class HitCounter: def __init__(self): # 使用双端队列存储时间戳 self.queue deque() def hit(self, timestamp: int) - None: # 将当前时间戳加入队列 self.queue.append(timestamp) def getHits(self, timestamp: int) - int: # 计算时间窗口的起始时间过去 300 秒 start_time timestamp - 300 # 移除所有过期的时间戳 while self.queue and self.queue[0] start_time: self.queue.popleft() # 返回队列中剩余元素的个数 return len(self.queue) # Your HitCounter object will be instantiated and called as such: # obj HitCounter() # obj.hit(timestamp) # param_2 obj.getHits(timestamp)关键实现细节为什么用while而不是if一次getHits调用后可能积累了多个过期时间戳例如长时间未查询、期间发生了大量命中需要循环移除队头所有 start_time的元素为什么移除条件是而不是getHits(timestamp)统计的是过去 300 秒内的命中窗口左边界为timestamp - 300窗口为开区间(timestamp - 300, timestamp]因此恰好等于start_time的命中已经过期必须被移除popleft语义deque.popleft()从队头移除并返回元素时间复杂度 O(1)满足高频出队需求。复杂度分析时间复杂度hit操作O(1)只需将元素加入队尾getHits操作O(k)其中 k 是需要移除的过期时间戳数量。空间复杂度O(n)其中 n 是在过去 300 秒内的敲击次数。源码级印证仓库中的队列实现该解法依赖的「双端队列 队头淘汰 队尾追加」正是仓库队列章节的核心数据结构。在 codes/python/03_stack_queue_hash_table/queue_deque.py 中可以看到双端队列两种存储方式的具体实现链式存储Deque基于双向链表通过头尾哨兵节点head/tail实现 O(1) 的push_back队尾入队与pop_front队头出队与题解中queue.append/queue.popleft的语义一一对应顺序存储ArrayDeque基于数组与取模运算实现循环队列front指向队头、rear指向队尾pop_front时队头指针向后移动一位同样以 O(1) 完成队头淘汰。从源码结构看本题的deque方案正是把「双端队列的队尾入队 队头出队」能力直接复用到时间窗口场景入队代表一次命中出队代表一次过期。这也解释了为什么hit能稳定达到 O(1)——双端队列的两端操作本身就是 O(1) 的。仓库中 03_03_queue_basic.md 还介绍了顺序存储队列与链式存储队列的完整实现顺序队列存在假溢出问题需要通过循环队列解决链式队列则天然无容量限制、适合频繁插入删除的场景。本题deque的链式实现在大量命中时不会因扩容而抖动是更稳妥的选择。同类题目对照数据流中的移动平均值「敲击计数器」与仓库中 0346. 数据流中的移动平均值 属于同一类队列 滑动窗口设计题移动平均值固定窗口大小size通过「队满先出队、再入队」维护固定长度窗口敲击计数器则按时间戳动态淘汰过期元素窗口长度随时间推进而收缩。两者共同体现的设计模式是用队列维持时间/数据的有序性配合窗口边界条件完成元素的进出。区别在于敲击计数器的出队条件不依赖队列长度而是依赖时间戳与当前时刻的差值。进阶思考每秒敲击次数很大怎么办原题进阶问题——如果每秒的敲击次数是一个很大的数字你的计数器可以应对吗——直指队列方案的空间短板队列方案的空间复杂度 O(n) 与过去 300 秒内的敲击次数成正比。如果每秒敲击数极大例如每秒百万次300 秒内队列将膨胀到数亿量级内存无法承受可以推断的优化方向是将「逐次记录时间戳」改为「按秒聚合计数」既然窗口固定为 300 秒可以维护一个长度为 300 的环形数组桶每个桶记录该秒发生的敲击次数并用mod 300的取模运算循环覆盖旧桶。此时hit(timestamp)将timestamp % 300对应桶计数加 1O(1)getHits(timestamp)累加 300 个桶的计数并减去被覆盖的过期部分O(1)需额外维护总数与覆盖标记。该思路与仓库中ArrayDeque的循环指针思想同源——用取模运算在固定大小数组上循环复用存储空间将空间复杂度从 O(n) 压缩到 O(1)从而应对海量敲击的高频场景。不过需注意环形数组方案要求记录每个桶的最新时间戳以便判断该桶是否过期这是与原题队列方案的主要差异点。总结维度结论数据结构选型双端队列FIFO与时间戳单调递增特性天然契合hit 操作队尾追加O(1)getHits 操作循环移除过期队头后返回队列长度均摊高效空间占用O(窗口内命中次数)可通过环形计数数组优化为 O(1)「敲击计数器」是面试中经典的「设计题 队列」组合它检验的不只是队列 API 的使用更是对如何用数据结构表达时间窗口这一抽象能力的理解。掌握队列版解法后再结合环形计数数组的优化思路即可完整覆盖该题的考察点。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐用栈实现队列LeetCode 0232双栈均摊 O(1) 队列设计解析 —— AlgoNote 算法通关手册用栈实现队列LeetCode 0232双栈均摊 O 1 队列设计解析 —— AlgoNote 算法通关手册 导读 本篇技术指南围绕「LeetCode 02教程文档知识库AlgoNote 算法通关手册优先队列Priority Queue原理、二叉堆实现与 LeetCode 实战AlgoNote 算法通关手册优先队列Priority Queue原理、二叉堆实现与 LeetCode 实战 优先队列是一种按「优先级高者先出」出队的数据教程文档知识库Pandoc OpenDocument 列表渲染解析从 Markdown 嵌套列表到 ODT 的 text:list 结构Pandoc OpenDocument 列表渲染解析从 Markdown 嵌套列表到 ODT 的 text:list 结构 导读 本篇文章以 Pandoc教程文档知识库上一篇深入解析 OpenReplay 集成的 HashiCorp Vault Helm Chart0.1.0 至 0.22.1 的演进脉络与配置实践下一篇开源协作实践指南从 Fork 到 Merge 的完整贡献流程与 easy-vibe 项目实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
AlgoNote 算法通关手册：LeetCode 362 敲击计数器（Design Hit Counter）——用队列实现 5 分钟窗口命中统计
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」中 0362. 敲击计数器 的完整技术解析围绕统计过去 5 分钟300 秒内敲击次数这一经典数据流计数问题讲解基于队列的滑动窗口实现并结合仓库中队列源码剖析其底层原理。读完本文你将掌握队列在时间窗口统计场景下的建模方法理解hit与getHits两个操作的时间复杂度来源并能够应对每秒敲击次数很大的进阶优化思路。题目概述题目0362. 敲击计数器Design Hit Counter标签设计、队列、数组、二分查找、数据流难度中等题目链接见 docs/solutions/0300-0399/index.md 中 0362 条目题目要求设计一个敲击计数器HitCounter使其能够统计在过去5 分钟即过去300 秒内发生的敲击次数。系统接受一个以秒为单位的时间戳参数timestamp并且可以假定所有调用按时间顺序进行即timestamp单调递增几次敲击可能同时发生。需要实现HitCounter类方法说明HitCounter()初始化命中计数器系统void hit(int timestamp)记录在timestamp单位秒发生的一次命中同一个timestamp中可能出现多次点击int getHits(int timestamp)返回timestamp在过去 5 分钟内即过去 300 秒的命中次数约束说明1 timestamp 2 * 10^9所有对系统的调用都是按时间顺序进行的timestamp单调递增hit和getHits最多被调用 300 次进阶如果每秒的敲击次数是一个很大的数字计数器还能应对吗示例演示输入 [HitCounter, hit, hit, hit, getHits, hit, getHits, getHits] [[], [1], [2], [3], [4], [300], [300], [301]] 输出 [null, null, null, null, 3, null, 4, 3]解释HitCounter counter new HitCounter(); counter.hit(1); // 在时刻 1 敲击一次 counter.hit(2); // 在时刻 2 敲击一次 counter.hit(3); // 在时刻 3 敲击一次 counter.getHits(4); // 在时刻 4 统计过去 5 分钟内的敲击次数返回 3 counter.hit(300); // 在时刻 300 敲击一次 counter.getHits(300);// 在时刻 300 统计过去 5 分钟内的敲击次数返回 4 counter.getHits(301);// 在时刻 301 统计过去 5 分钟内的敲击次数返回 3注意最后一次调用在时刻 301 时时刻 1 已经超出 300 秒窗口301 - 300 1窗口要求严格大于 1因此命中的是时刻 2、3、300 三次返回 3。解题思路 1基于队列的滑动窗口核心建模窗口统计问题的本质是维护一段长度为 300 秒的时间区间内的数据。由于调用时间戳单调递增所有命中事件天然构成一个按时间排序的序列这与队列「先进先出FIFO」的特性完全吻合最先发生的命中最早过期应当最先被移除队头出队最新发生的命中在窗口内存活时间最长应当最后被移除队尾入队。因此可以用一个队列存储所有敲击时间戳队列中的元素天然按时间戳升序排列。具体步骤初始化创建一个空队列queue用于存储时间戳hit 操作将当前时间戳timestamp加入队列队尾入队getHits 操作计算时间窗口的起始时间start_time timestamp - 300移除队列中所有小于等于start_time的时间戳过期命中队头出队返回队列中剩余元素的个数即为过去 300 秒内的命中次数。参考代码from collections import deque class HitCounter: def __init__(self): # 使用双端队列存储时间戳 self.queue deque() def hit(self, timestamp: int) - None: # 将当前时间戳加入队列 self.queue.append(timestamp) def getHits(self, timestamp: int) - int: # 计算时间窗口的起始时间过去 300 秒 start_time timestamp - 300 # 移除所有过期的时间戳 while self.queue and self.queue[0] start_time: self.queue.popleft() # 返回队列中剩余元素的个数 return len(self.queue) # Your HitCounter object will be instantiated and called as such: # obj HitCounter() # obj.hit(timestamp) # param_2 obj.getHits(timestamp)关键实现细节为什么用while而不是if一次getHits调用后可能积累了多个过期时间戳例如长时间未查询、期间发生了大量命中需要循环移除队头所有 start_time的元素为什么移除条件是而不是getHits(timestamp)统计的是过去 300 秒内的命中窗口左边界为timestamp - 300窗口为开区间(timestamp - 300, timestamp]因此恰好等于start_time的命中已经过期必须被移除popleft语义deque.popleft()从队头移除并返回元素时间复杂度 O(1)满足高频出队需求。复杂度分析时间复杂度hit操作O(1)只需将元素加入队尾getHits操作O(k)其中 k 是需要移除的过期时间戳数量。空间复杂度O(n)其中 n 是在过去 300 秒内的敲击次数。源码级印证仓库中的队列实现该解法依赖的「双端队列 队头淘汰 队尾追加」正是仓库队列章节的核心数据结构。在 codes/python/03_stack_queue_hash_table/queue_deque.py 中可以看到双端队列两种存储方式的具体实现链式存储Deque基于双向链表通过头尾哨兵节点head/tail实现 O(1) 的push_back队尾入队与pop_front队头出队与题解中queue.append/queue.popleft的语义一一对应顺序存储ArrayDeque基于数组与取模运算实现循环队列front指向队头、rear指向队尾pop_front时队头指针向后移动一位同样以 O(1) 完成队头淘汰。从源码结构看本题的deque方案正是把「双端队列的队尾入队 队头出队」能力直接复用到时间窗口场景入队代表一次命中出队代表一次过期。这也解释了为什么hit能稳定达到 O(1)——双端队列的两端操作本身就是 O(1) 的。仓库中 03_03_queue_basic.md 还介绍了顺序存储队列与链式存储队列的完整实现顺序队列存在假溢出问题需要通过循环队列解决链式队列则天然无容量限制、适合频繁插入删除的场景。本题deque的链式实现在大量命中时不会因扩容而抖动是更稳妥的选择。同类题目对照数据流中的移动平均值「敲击计数器」与仓库中 0346. 数据流中的移动平均值 属于同一类队列 滑动窗口设计题移动平均值固定窗口大小size通过「队满先出队、再入队」维护固定长度窗口敲击计数器则按时间戳动态淘汰过期元素窗口长度随时间推进而收缩。两者共同体现的设计模式是用队列维持时间/数据的有序性配合窗口边界条件完成元素的进出。区别在于敲击计数器的出队条件不依赖队列长度而是依赖时间戳与当前时刻的差值。进阶思考每秒敲击次数很大怎么办原题进阶问题——如果每秒的敲击次数是一个很大的数字你的计数器可以应对吗——直指队列方案的空间短板队列方案的空间复杂度 O(n) 与过去 300 秒内的敲击次数成正比。如果每秒敲击数极大例如每秒百万次300 秒内队列将膨胀到数亿量级内存无法承受可以推断的优化方向是将「逐次记录时间戳」改为「按秒聚合计数」既然窗口固定为 300 秒可以维护一个长度为 300 的环形数组桶每个桶记录该秒发生的敲击次数并用mod 300的取模运算循环覆盖旧桶。此时hit(timestamp)将timestamp % 300对应桶计数加 1O(1)getHits(timestamp)累加 300 个桶的计数并减去被覆盖的过期部分O(1)需额外维护总数与覆盖标记。该思路与仓库中ArrayDeque的循环指针思想同源——用取模运算在固定大小数组上循环复用存储空间将空间复杂度从 O(n) 压缩到 O(1)从而应对海量敲击的高频场景。不过需注意环形数组方案要求记录每个桶的最新时间戳以便判断该桶是否过期这是与原题队列方案的主要差异点。总结维度结论数据结构选型双端队列FIFO与时间戳单调递增特性天然契合hit 操作队尾追加O(1)getHits 操作循环移除过期队头后返回队列长度均摊高效空间占用O(窗口内命中次数)可通过环形计数数组优化为 O(1)「敲击计数器」是面试中经典的「设计题 队列」组合它检验的不只是队列 API 的使用更是对如何用数据结构表达时间窗口这一抽象能力的理解。掌握队列版解法后再结合环形计数数组的优化思路即可完整覆盖该题的考察点。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐用栈实现队列LeetCode 0232双栈均摊 O(1) 队列设计解析 —— AlgoNote 算法通关手册用栈实现队列LeetCode 0232双栈均摊 O 1 队列设计解析 —— AlgoNote 算法通关手册 导读 本篇技术指南围绕「LeetCode 02教程文档知识库AlgoNote 算法通关手册优先队列Priority Queue原理、二叉堆实现与 LeetCode 实战AlgoNote 算法通关手册优先队列Priority Queue原理、二叉堆实现与 LeetCode 实战 优先队列是一种按「优先级高者先出」出队的数据教程文档知识库Pandoc OpenDocument 列表渲染解析从 Markdown 嵌套列表到 ODT 的 text:list 结构Pandoc OpenDocument 列表渲染解析从 Markdown 嵌套列表到 ODT 的 text:list 结构 导读 本篇文章以 Pandoc教程文档知识库上一篇深入解析 OpenReplay 集成的 HashiCorp Vault Helm Chart0.1.0 至 0.22.1 的演进脉络与配置实践下一篇开源协作实践指南从 Fork 到 Merge 的完整贡献流程与 easy-vibe 项目实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考