1. 先读懂题日志统计到底在考什么1.1 原题描述与数据范围日志统计这道题说的是某个论坛有大量点赞记录每一行是一条日志格式是两个整数时刻 ts 和帖子编号 id。题目给三个参数 N、D、K要求把所有热帖的 id 找出来并从小到大输出。热帖的定义是存在某个长度 D 的时间段在这个时间段内该帖子收到的赞不少于 K 个。在不少OJ题库里这个题被标成题目2279属于2018年第九届蓝桥杯的省赛真题。这道题看起来场景非常生活化但实际考核的知识点很聚焦。我印象里数据规模一般在十万量级N 可以到 10^5帖子 id 也在这个规模附近时间戳可以不连续甚至很大。正因为数据规模不小解题才必须从排序和线性扫描入手。你要是拿到题第一时间想的是对每个帖子维护一长串时间戳再去枚举窗口起点十有八九会超时。先把这个定义和量级留在脑子里后面所有设计都围绕它展开。从历年的反馈来看这道题在省赛里区分度其实挺高。会的人十分钟能交代码不会的人能在暴力和各种边界条件里绕两个小时。它不是靠背模板就能混过去的题而是考察你能不能把一个模糊的任意时间段描述翻译成精确的、可枚举的算法条件。1.2 别急着写暴力为什么 O(n^2) 一定会超时很多同学第一次做这题第一个想法是把日志按帖子分组每组按时间排序然后从第一条开始往后数看 D 时间段内够不够 K 个。这个思路方向是对的但它本质上是在每个帖子的时间戳序列里做滑窗实现得好确实能过。但有不少人写成了这样枚举每一条点赞记录作为窗口左端点然后往右扫描直到时间差超过 D再统计这段区间里这条帖子出现多少次。最坏情况下一条帖子在整段时间里频繁点赞或者所有帖子都集中在同一小段时间里内层扫描的规模会被拉满总复杂度直接到 O(N^2)。在 N10^5 的数据下这意味着可能跑出 10^10 次级别的基本操作蓝桥杯评测机虽然不至于严格卡常数但稳挂是跑不掉的。我见过一位选手写了这种暴力解法交上去大数据直接 TLE他来问我的时候还挺委屈说我思路完全没问题就是慢了一点。我让他随便构造一个单帖子连续点赞两万次的测试数据他跑了一下循环次数直接奔着四亿次去了这还没算排序的开销。真正的解法必须保证只遍历一遍日志序列而且每个日志只进窗口一次、出窗口一次整体复杂度做到 O(N log N) 或 O(N)。1.3 把任意时间段翻译成可操作的条件热帖定义里最麻烦的其实是任意长度 D 的时间段这六个字。时间轴是连续的你不可能真的枚举每一个可能的起点 T。换个角度想一个帖子要想成为热帖它一定有一组赞落在某个长度为 D 的区间里。那么我们干脆把这组赞里最靠右的那个赞找出来当作锚点。假设锚点时刻是 tr那么在这个区间里出现的所有赞时刻都不可能早于 tr 减去 D准确说是它们与 tr 的时间差严格小于 D。反过来只要存在一个时刻 tr在 [tr-D, tr] 这个范围内该帖子的赞数不少于 K那它就满足条件了。这听起来有点像废话但它把任意起点的问题转化成了固定右端点的问题一下子就有了枚举的基础。排序之后问题就变成一个很经典的双指针维护区间问题把所有日志按时间排好从前往后扫用一个左指针卡住区间的左边界使得右指针扫过的区间始终满足跨度不超过 D。每次右指针新增一条日志就在计数桶里把对应帖子数加一左指针负责把太老的、已经超出 D 范围的日志从计数里减掉。这样我们根本没有枚举窗口起点而是让窗口自动随右端点前进而移动所有满足条件的帖子在这个过程中都会被自然标记出来。这个思路是整道题的核心也是后面所有代码的共同骨架。2. 核心算法双指针加桶计数2.1 排序之后发生了什么想象你把日志按时间排成一行现在它们不再是孤立的事件而是一条时间线。此时我们要找的热帖就变成在时间线上存在一段连续区域区域宽度小于或等于 D区域里某个 id 出现的次数达到了 K。注意这个区域不要求长度刚好等于 D只要不超过 D 就行因为题意是存在某个长度 D 的时间段如果一个更短的区间里已经凑够了 K 个赞那它当然也存在于某个长度为 D 的时间段里。这里有一个新手很容易误解的细节题目说长度 D 的时间段在标程和绝大多数题解里默认采用的是半开区间 [T, TD) 的语义也就是里面的时间戳 t 满足 T t TD。因此任意两条在同一窗口内的日志时间差是严格小于 D 的。如果你把判断写成小于等于得到的窗口会偏大可能把本不该算进去的记录算进去边界数据一测就露馅。这个细节我在后面的踩坑章节还会重点讲。所以我们要维护的窗口就三个核心属性左指针 l、右指针 r、窗口内日志的时间跨度 logs[r].ts - logs[l].ts。当这个跨度达到或超过 D 时说明窗口已经撑破题目允许的长度必须把 logs[l] 从计数里扣除然后 l 加一直到跨度重新小于 D。因为右端点每扫一步只挪一格左端点最多也同步挪 N 次所以这个窗口的总维护成本是 O(N)非常干净。2.2 指针移动的时机与依据直接看伪代码把所有动作串一遍。sort(logs by time) l 0 cnt {} hot {} for r in 0..N-1: id_r logs[r].id cnt[id_r] 1 while logs[r].ts - logs[l].ts D: id_l logs[l].id cnt[id_l] - 1 if cnt[id_l] 0: 从cnt里删掉这个键 l 1 if cnt[id_r] K: hot.add(id_r) 输出 hot 排序后的结果我建议把先加后收缩写成固定模式。如果你写成先收缩再加逻辑上也是等价的但你需要额外小心收缩时左指针会不会正好指到刚加入的那条日志不会因为当前新日志和它自己的时间差是0收缩条件不可能成立。所以两种顺序都对。但我个人更推荐先加后收缩因为可以确保新日志一定参与计数思考负担小很多代码也更不容易在边界上出错。收缩条件用 D而不是 D这一点只要题目按半开区间定义就没错。判断热帖的时机也有讲究。很多解法会在 cnt 更新完以后把当前窗口里所有帖子的计数都检查一遍那当然能过但完全没必要。其实只需要检查新加入的这一条日志的 id 就够了。原因前面说过如果存在满足条件的时间段那么在这个时间段内最靠右那条日志被扫到时当前窗口一定把所有在该时间段内的赞都包进来了cnt[id_r] 这时候必然大于等于 K。你不检查 id_r 而只检查别的 id反而可能漏掉。2.3 判定热帖的边界细节这里有几个边界处理不好样例过了也不代表能过评测。第一条只有一条日志的情况。N1如果 K1 且 D 是任意正数cnt 初始为0加1后是1标记没问题如果 K2cnt 是1不标记同样符合题意。第二条两条日志时间差恰好等于 D。按照 D收缩会把第一条从窗口里剔除于是第二条不能和第一条凑到一个窗口这也符合半开区间的定义。如果原题想表达的是闭区间不超过 D那么应该写成 D时收缩即允许差为 D 的两条日志在同一个窗口。蓝桥杯这道题的标程和绝大多数题解用的都是差小于 D 判断在窗内也就是我这里的 D收缩。第三条同一时刻有多条日志。排序后它们必然挨在一起时间差为0全部可以放在同一个窗口。如果是同一个 id 在同一时刻被点了多次赞计数逻辑照常累加不会出现冲突。第四条id 不连续甚至很大。如果用数组做计数桶数组大小一定要按 id 上限开别只开 N 的大小如果不确定上限就用哈希表。数组有数组的好处哈希表有哈希表的稳妥我在下一章给三种语言的完整实现。3. 完整代码实现与复杂度分析3.1 C 实现蓝桥杯 C 组最稳妥的做法是直接用数组当计数桶因为数组比哈希表快代码也短。我先按 id 上限已知的情况来写。如果你不确定上限可以把数组换成 unordered_map核心逻辑完全不变。#include bits/stdc.h using namespace std; struct Log { int ts, id; bool operator(const Log o) const { return ts o.ts; } }; const int MAXID 1000005; int cnt[MAXID]; bool hot[MAXID]; int main() { int n, d, k; scanf(%d%d%d, n, d, k); vectorLog logs(n); for (int i 0; i n; i) { scanf(%d%d, logs[i].ts, logs[i].id); } sort(logs.begin(), logs.end()); int l 0; for (int r 0; r n; r) { int id logs[r].id; cnt[id]; while (logs[r].ts - logs[l].ts d) { --cnt[logs[l].id]; l; } if (cnt[id] k) { hot[id] true; } } for (int i 0; i MAXID; i) { if (hot[i]) { printf(%d\n, i); } } return 0; }这段代码有几个细节你提交前要检查MAXID 必须大于所有可能出现的 id如果题目没有给出 id 上限这个方案就不够严谨。另外标记热帖我用了一个 bool 数组如果 id 上限很大但实际出现很少最后遍历整个数组会浪费一些时间。更常见的做法是最后把所有标记过的 id 收集进 vector 再排序输出这样能自适应任意 id 范围也更符合从小到大输出的天然思路。我平时写比赛题更推荐用 unordered_set 存热帖最后复制到 vector 排序。代码会稍微多两行但不会因为数组开小了而出错心里踏实。3.2 Java 实现Java 组没有 C 那么方便开大数组但完全可以用 HashMap 当计数桶。另一个注意点输出要求从小到大我直接用 TreeSet 存热帖 id省得最后再排序一遍。import java.util.*; public class Main { static class Log implements ComparableLog { int ts, id; Log(int ts, int id) { this.ts ts; this.id id; } public int compareTo(Log o) { return this.ts - o.ts; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int d sc.nextInt(); int k sc.nextInt(); ListLog logs new ArrayList(); for (int i 0; i n; i) { logs.add(new Log(sc.nextInt(), sc.nextInt())); } Collections.sort(logs); MapInteger, Integer cnt new HashMap(); TreeSetInteger hot new TreeSet(); int l 0; for (int r 0; r n; r) { int curId logs.get(r).id; cnt.put(curId, cnt.getOrDefault(curId, 0) 1); while (logs.get(r).ts - logs.get(l).ts d) { int oldId logs.get(l).id; int val cnt.get(oldId) - 1; if (val 0) { cnt.remove(oldId); } else { cnt.put(oldId, val); } l; } if (cnt.get(curId) k) { hot.add(curId); } } StringBuilder sb new StringBuilder(); for (int id : hot) { sb.append(id).append(\n); } System.out.print(sb); } }有个细节值得说明当 cnt[oldId] 被减到 0 时我建议直接 remove 掉。如果不 remove后面 getOrDefault 时拿到的旧值都是 0不会影响 cnt.get(curId) 的判断但会多占空间而且调试时打印 HashMap 会看到一堆零值残留根本分不清哪些帖子真的在窗口内。减完就删是写哈希计数器的好习惯Java 里要注意不能边遍历边修改这里我们只是按 key 取值再 put是安全的。3.3 Python 实现与复杂度对比Python 写竞赛题常被吐槽慢但这道题是排序加线性扫描N 在十万级别时蓝桥杯的 Python 评测环境是可以跑动的。记得用 sys.stdin.buffer 做输入能省下不少时间。import sys from collections import Counter def main(): data sys.stdin.buffer.read().split() n int(data[0]) d int(data[1]) k int(data[2]) logs [] idx 3 for _ in range(n): ts int(data[idx]) pid int(data[idx 1]) logs.append((ts, pid)) idx 2 logs.sort() cnt Counter() hot set() l 0 for r in range(n): ts_r, pid_r logs[r] cnt[pid_r] 1 while logs[r][0] - logs[l][0] d: old_pid logs[l][1] cnt[old_pid] - 1 if cnt[old_pid] 0: del cnt[old_pid] l 1 if cnt[pid_r] k: hot.add(pid_r) print(\n.join(str(x) for x in sorted(hot))) if __name__ __main__: main()Counter 本身就是一个计数器减到 0 不删除也不会影响判断但我同样建议删除保持语义清楚。Python 的 while 条件里反复用logs[r][0]和logs[l][0]做索引速度会稍微慢一点但 N 不大时无伤大雅。如果你追求极限性能可以先把 logs 拆成两个独立的数组 ts_list 和 id_list分别按下标访问速度会明显提升。三种语言的实现逻辑完全一样区别只在于计数结构的选择。我平时给人讲这道题最后都会给一张这样的对比表方便他选自己熟悉的语言环境去复现语言计数结构复杂度说明C数组或 unordered_mapO(N log N)内存可控速度最快JavaHashMapO(N log N)代码略长但输出借助 TreeSet 很稳PythonCounterO(N log N)编码最快适合刷题验证思路到了考场上选哪个语言不重要重要的是你是不是真的理解了同一套双指针逻辑。别因为代码风格差异大就怀疑自己的思路本质上是同一个东西。4. 实战踩坑与调试实录4.1 窗口长度到底是 D 还是 D 减一这是我看到最多人翻车的点。题目里描述连续时间段内长度 D从离散角度理解会出现歧义时间点 0 和时间点 2如果 D2算不算在同一个长度为 2 的区间里有的选手觉得 2-02当然算然后他写 D收缩结果边界样本全部算错。蓝桥杯这道题在主流解法里采用半开区间 [T, TD)也就是窗口内任意两条日志的时间差严格小于 D。你可以自己验证如果两条日志时间差刚好等于 D那么长度为 D 的半开区间装不下它们必须把它们分到两个窗口。如果你改成 D收缩就会把差等于 D 的两个点强行放一个窗口答案会多出一些帖子。所以我的建议是先按 D收缩写一遍再用边界数据自测。如果你能从题目原文明确读出闭区间的意思再改成 D。不要凭感觉改条件改之前先想清楚这个区间是包含端点还是不包含端点。4.2 同时间为一个帖子多次点赞怎么办这算一个高频的输入细节。有些题目会在数据说明里保证 ts 和 id 的组合唯一但很多时候没有这种承诺。如果同一个帖子在同一时刻被点了三个赞按我们的逻辑排序后这三条日志时间差为 0全部进同一个窗口cnt 会累加到 3只要 K3 就能标记没有任何问题。反过来如果题目保证每个时刻每个帖子最多一条赞那我们的代码也完全兼容。所以不需要提前做聚合强行合并反而容易算错。你只要把每个 (ts, id) 当成独立的一条日志按输入顺序处理就行算法天然支持重复数据。4.3 哈希表的删除与残留计数前面 Java 和 Python 部分我都反复提了减完就删。有一个真实案例有位同学用 HashMap 写完后把 cnt.remove(oldId) 写成了只 cnt.put(oldId, 0)理论上结果也应该对因为他判断用的 getOrDefault 和 get 都不受零值影响。但问题出在调试上打印 HashMap 的时候你会看到大量 id 对应的计数是 0你根本分不清哪些帖子真的在窗口内哪些已经被移出去了。半夜调题本来就容易烦躁这种残留数据会浪费你大量时间。另外还有一个小坑如果你在 Java 里用 TreeMap每次 get 和 put 都是 O(log M) 的整体复杂度会多一个 log在这道题的规模下不会超时但如果你还用 TreeMap 遍历整个 key 集合性能会差一些。直接用 HashMap 计数最后用 TreeSet 存热帖 id是性能和代码简洁之间的最好平衡。4.4 输出顺序与答案去重题目明确要求从小到大输出而且一个热帖只能输出一次哪怕它被标记了很多次。我看到有同学把 hot 设成数组后在扫描时把 hot[id]true最后从 1 到 MAXID 全部打印这个思路对前提是数组开得够大。真正的坑是他把 MAXID 开小了比如 id 最大 100000他只开了 50005然后几个大数据直接数组越界评测反馈是 WA 而不是 RE排查起来特别迷惑。所以做这类题我推荐一个原则能不开全局裸数组就不开热帖集合用 set 收集最后排序或者利用自带有序结构输出。这样 id 范围随便多大都能处理代码的健壮性也更好。4.5 调试日志的技巧有时候样例过了但提交就是 WA我的排查顺序一般这样先打印排序后的 logs 前二十条看时间戳是否排对了再打印每次 r 移动后的窗口边界 l 和 cnt 内容肉眼确认窗口跨度有没有超过 D最后写一个暴力验证函数跑 N 比较小的随机数据和双指针结果对拍。随机数据我一般这么生成N100D5K3ts 取 0 到 9id 取 1 到 5。这样基本不需要几秒钟就能看出逻辑错在哪里。暴力函数很简单枚举每个起始时刻、每个帖子统计只要能对上就说明核心逻辑稳了。这个方法在几乎所有滑动窗口题里都好用。4.6 常见问题速查表现象可能原因排查方向结果里少了边界帖子窗口收缩条件误写成 D导致可覆盖的边界被剔除改回 D输出重复没有去重hot 用了非集合结构改用 Set 或 bool 标记TLE使用了 O(N^2) 枚举窗口起点换成双指针RE 或 WA计数数组开太小id 越界改用哈希表或增大数组结果全部为空忘记处理 K1 的情况跑最小样例 N1, K1这张表是我反复带人做这题之后总结出来的每年都有大量人在这些边界上翻车提前对照一遍能省下大量调题时间。你甚至可以把它当作一个检查清单每次写完滑窗题都过一遍。5. 从这题提炼出的竞赛方法论5.1 滑动窗口题的识别特征以后再做历届蓝桥杯真题看到连续、时间段、窗口、至少 K 个这些描述词第一反应就该是滑动窗口。这类题通常出现在需要统计一个序列上子区间特征的问题里。判断条件有三个问题要求的是连续子区间区间的起点不需要逐一枚举数据规模在一万以上、十万上下。只要三个都满足双指针基本就是正解方向。如果不确定可以先用暴力思路跑小数据再用滑窗思路跑随机数据对拍几分钟就能验证。刷题多的人会发现蓝桥杯省赛里大量题都是这套模板换了一层生活化的外衣剥开之后全是熟人。5.2 对其他题目的迁移应用日志统计的写法可以原封不动套用到很多题上。比如统计每个长度不超过 L 的窗口里出现次数最多的数代码几乎一样只是最后输出改成维护一个最大值再比如找最小区间使得覆盖所有颜色左指针收缩的条件变成某种颜色的计数多余而需要删也是同一套双指针模板还有经典的最长无重复子串本质就是用一个窗口维护没有重复字符的区间。我建议你把这题的代码模板背熟因为它是滑动窗口里最干净的形态。先加右端点再收缩左端点最后检查端点这个三步动作适用于绝大多数双指针问题。把这套动作练成肌肉记忆考试时看到类似描述你甚至不用思考就能写出主循环。5.3 一些写给备赛同学的建议最后说几句可能很多人不爱听但确实有用的话。第一刷题别只看题解自己敲一遍再 debug 一遍比看十遍题解都强。日志统计这题我指导过不少学弟学妹只要让他们亲手敲一遍他们对双指针的理解立刻上一个台阶。第二自己造数据的时候一定要造边界D 恰好等于两条日志的时间差、N1、KN 这些都要测。第三代码里的注释别少写尤其像窗口长度条件这种最容易忘的地方写上半开区间差小于 D几个字下次再看就能秒懂。第四比赛时如果时间不够先用双指针模板写出主逻辑再补输出细节不要花大量时间纠结数组到底开多大。这道题我前前后后带人做了不下十遍每一次都会发现新的小坑。个人体会是真正难的从来不是双指针本身而是你能否把题目描述的任意时间段转换成可枚举的窗口端点。把这个转换想通日志统计就是一道送分题想不通它就能卡你两小时。做题嘛最值钱的就是这种想通的过程。