日志统计这道题蓝桥杯第九届省赛的经典题目OJ编号2279我在备赛期间反复刷过好几遍也在赛场上见过不少同学在这里丢分。题目本身不复杂数据范围却卡得恰到好处——把一批只会暴力枚举的人挡在门外。今天就把这题从读题到代码实现完整拆开讲一遍包括常见的边界坑、排序细节、双指针写法以及三种主流语言的实现差异希望能帮还在刷真题的人彻底吃透它。1. 题目2279到底在说什么日志统计的题面与核心矛盾1.1 题面原貌与输入输出规则先还原一下题目描述。小明维护着一个程序员论坛论坛有 N 条点赞记录每条记录包含两个整数时间 ts 和帖子编号 id表示编号为 id 的帖子在 ts 时刻收到了一次点赞。现在小明想知道哪些帖子曾经是“热帖”判断标准是如果存在一个任意长度为 D 的时间段在这个时间段内某个帖子收到的赞数不少于 K 个那么它就是热帖。要求按 id 从小到大输出所有热帖的编号每个 id 占一行。输入格式不复杂第一行是三个整数 N、D、K接下来 N 行每行两个整数 ts 和 id。数据范围我记得很清楚N、D、K 都能到 100000ts 和 id 也都在 1 到 100000 区间内。这意味着什么O(N乘D) 的复杂度一定超时O(N^2) 的复杂度更是想都不要想。题目给的限制有意引导你往线性或 O(N log N) 的思路上靠。1.2 表面是一道模拟题本质是滑动窗口很多第一次做这题的人会陷入一种直觉枚举每个时间段的起点再统计该时间窗口内的所有记录。这个思路看起来没毛病但一旦 N 是十万D 是十万你就算枚举每个帖子、每个可能的时间窗口总计算量轻松超过十的十次方。比赛环境根本不可能放你过去。这题真正的考察点在于日志记录本质上是按时间先后顺序发生的。如果我们把 N 条记录按时间排序那么“任意长度为 D 的时间段”就变成了排序后一维坐标轴上的一个区间。维护这个区间里各个 id 的点赞次数区间右端点每次扩展一条记录左端点根据时间差不断收缩整个过程只需要每条记录进出窗口一次。这就是经典的滑动窗口双指针思路和单调队列、尺取法的本质是一脉相承的。理解了这个核心矛盾题目就成功了一大半。下面从复杂度开始认真推导。2. 暴力做法为什么必挂从N1e5看时间复杂度的生死线2.1 最常见的错误思路按时间段枚举加统计拿到题目第一反应通常是枚举每个时间段起点 L终点 LD然后扫一遍所有记录统计在时间区间内的每个 id 点了几次赞。假设时间范围最大也是 1e5枚举一次起点是 1e5扫描记录是 1e5这里还没算上统计和比较 K 的额外开销仅仅是这两层循环就已经是 1e10 次基本操作了。1e10 是什么概念普通服务器一秒钟大约只能跑 1e8 到 1e9 次简单运算这种写法跑完需要几分钟甚至更久在竞赛环境中大概率直接超时。也有人说我改进一下枚举帖子 id 和窗口起点然后用前缀和或者差分。这个思路能优化统计开销但是你要为每个 id 维护一个时间轴前缀数组id 范围也是 1e5前缀数组就得开到 1e10 个整数内存直接爆掉显然不可行。所以问题的复杂度瓶颈不只在时间还在空间。2.2 双指针为什么能把复杂度拉到O(N log N)关键突破口在于时间段是连续的点赞记录也是按时间排序的一维序列。我们不需要为了每个 id 单独开时间轴而是可以用一个“全局窗口”去覆盖当前关注的时间区间。具体来说排序后记录数组下标为 left 和 right 的位置代表两条记录的时间。窗口内的时间范围就是 [time[left], time[right])关于开闭区间后面专门讲只要 time[right] - time[left] 小于 D这个窗口就是合法的。我们需要维护的是窗口内每个 id 的点赞次数 cnt[id]。right 每次向右移动一条新记录窗口内点赞次数就加一当时间跨度超过 D 时left 向右收缩同时把离开窗口的那条记录的 id 对应的计数减一。每次窗口变化后检查一下 cnt 里有没有达到 K 的 id有就标记为热帖。这样的过程right 从头走到尾最多移动 N 次left 同理最多移动 N 次每条记录进入和离开窗口各一次总操作量 O(N)。再算上排序的 O(N log N)整体复杂度就是 O(N log N)。N 为 1e5 时完全轻松跑进一秒这才是一个能拿满分的解法。理解了这个复杂度跳跃下面看具体实现。3. 双指针滑窗解法的三步拆解排序、扩窗、缩窗3.1 数据预处理按时间升序排序id保持原样排序是整个解法的基础。我们拿到的是无序的点赞记录需要先按照 ts 从小到大排列如果 ts 相同顺序其实无所谓因为后面判断时间差只看差值相同时间戳在窗口内同时存在即可。排序必须稳定吗不需要因为同一时间戳的记录互不影响谁前谁后不会改变最终统计结果。我习惯用一个结构体或者 Pair 存储记录然后按第一关键字时间排序。排序之后记录在数组中的相对位置就代表了时间先后关系之后所有窗口操作都在这个有序数组上进行。3.2 窗口扩展与收缩的动态维护双指针的核心其实就两个动作。首先right 指针从 0 开始向后扩展每遇到一条记录就把该记录的 id 计数加 1。此时窗口的右边界已经包含了这条记录。然后检查当前窗口时间跨度是否满足条件当 records[right].ts - records[left].ts D 时说明如果继续保留 left 所指的那条记录窗口时间跨度已经到达甚至超过 D不是题目要求的“长度 D 的时间段”了所以要把 left 记录的 id 计数减 1left 指针右移。这个过程不断重复直到时间跨度重新小于 D。这里最关键的细节是我们用的是什么开闭区间不同写法对 D 的理解直接影响答案。我采用的标准是“左闭右开”即窗口表示 [left_time, left_time D)。因为题目说“任意长度为 D 的时间段”时间段长度是 D那么两个端点的时间差必须严格小于 D才能确保它们同时落在一个长度为 D 的半开区间内。因此判断条件是 D 就收缩。如果误写成 D就会漏掉边界情况造成答案偏少这是历届很多人的失分点。3.3 热帖标记与去重什么时候判定热帖在 right 扩展完并完成 left 收缩修正后窗口内是一个合法的时间区间。这时候如果 cnt[某个 id] K就把它标记为热帖。标记方式一般有两种一种是用布尔数组 bool isHot[N]另一种是直接把 id 加入 set。考虑到最终按 id 升序输出布尔数组标记后最后再遍历一次 id 范围收集答案或者直接用集合去重再排序。有人会问同一个 id 在多个窗口内都可能达到 K 次重复标记会不会导致重复输出所以标记环节必须去重布尔数组天然解决这个问题。如果你用 set则自动去重但最后需要排序输出。实测下来布尔数组加最后遍历的效率稍高代码也更简单。4. 三种语言实现与调优细节C、Java、Python的实际差异4.1 C 版本stl排序加数组计数最标准的竞赛写法C 是竞赛主力语言实现起来也最直接。代码结构清晰用 vector 存 Pair排序然后滑动窗口。#include bits/stdc.h using namespace std; struct Log { int ts, id; }; 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(), [](const Log a, const Log b) { return a.ts b.ts; }); const int MAXID 100000; vectorint cnt(MAXID 1, 0); vectorbool hot(MAXID 1, false); int left 0; for (int right 0; right N; right) { int id logs[right].id; cnt[id]; while (logs[right].ts - logs[left].ts D) { cnt[logs[left].id]--; left; } if (cnt[id] K) { hot[id] true; } } for (int i 1; i MAXID; i) { if (hot[i]) printf(%d\n, i); } return 0; }几个值得注意的细节排序 lambda 里只比较了 ts如果 ts 相同保持原序没问题。while 收缩窗口时left 最多移动到 right不会越界因为 rightleft 时时间差恒为 0肯定小于 DD 为正整数。标记热帖放在收缩之后确保检查的一定是合法窗口。注意当前记录的 id 如果有增量并且达到 K就标记如果该 id 的赞数全靠窗口内其他记录达到 K也同样会被标记没问题。cnt 数组和 hot 数组按 id 最大值开题目没给明 id 上界时可以读完记录后取 maxId 动态开。竞赛中通常直接开大一点最省事。4.2 Java 版本实体类排序与数组初值处理Java 写这题要注意两点排序要用 Comparator 或 lambda数组自动初始化为 0布尔数组自动初始化为 false不需要手动初始化。代码大致如下import java.util.Arrays; import java.util.Scanner; public class Main { static class Log { int ts, id; Log(int ts, int id) { this.ts ts; this.id id; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int N sc.nextInt(); int D sc.nextInt(); int K sc.nextInt(); Log[] logs new Log[N]; for (int i 0; i N; i) { int ts sc.nextInt(); int id sc.nextInt(); logs[i] new Log(ts, id); } Arrays.sort(logs, (a, b) - a.ts - b.ts); int MAXID 100000; int[] cnt new int[MAXID 1]; boolean[] hot new boolean[MAXID 1]; int left 0; for (int right 0; right N; right) { cnt[logs[right].id]; while (logs[right].ts - logs[left].ts D) { cnt[logs[left].id]--; left; } if (cnt[logs[right].id] K) { hot[logs[right].id] true; } } StringBuilder sb new StringBuilder(); for (int i 1; i MAXID; i) { if (hot[i]) { sb.append(i).append(\n); } } System.out.print(sb); } }Scanner 比 BufferedReader 慢N 到 1e5 时 Scanner 其实还能扛住但保险起见可以用 BufferedReader StringTokenizer 解析输入。输出用 StringBuilder 拼接后一次性输出能省掉反复 System.out.println 的时间。4.3 Python 版本list排序与性能陷阱Python 在相同复杂度下运行耗时明显高于 C所以更要注意常数优化。思路相同直接用元组列表。import sys def main(): data sys.stdin.buffer.read().split() idx 0 N int(data[idx]); idx 1 D int(data[idx]); idx 1 K int(data[idx]); idx 1 logs [] for _ in range(N): ts int(data[idx]); idx 1 id_ int(data[idx]); idx 1 logs.append((ts, id_)) logs.sort(keylambda x: x[0]) MAXID 100000 cnt [0] * (MAXID 1) hot [False] * (MAXID 1) left 0 for right in range(N): cnt[logs[right][1]] 1 while logs[right][0] - logs[left][0] D: cnt[logs[left][1]] - 1 left 1 if cnt[logs[right][1]] K: hot[logs[right][1]] True out \n.join(str(i) for i in range(1, MAXID 1) if hot[i]) sys.stdout.write(out) if __name__ __main__: main()Python 的性能主要耗在排序和循环上N1e5 完全可控但如果你的环境里 Python 循环过慢可以考虑用数组模拟指针。还有一个 Python 特有的坑tuple 比较会先比 ts 再比 id我们 sort 不指定 key 其实也能得到按时间排序的结果但显式 keylambda x: x[0] 更清晰。用 sys.stdin.buffer.read() 一次性读取比逐行 input() 快很多这是我实测在蓝桥云课这种环境下能把运行时间压进一秒钟的关键。需要说明的是以上三种写法都是基于全局滑动窗口。还有一种常见的按帖子分组解法把每个 id 的点赞时间单独存一个列表每个列表排序后检查连续 K 个点赞的首尾时间差是否小于 D如果小于说明该帖子在某个 D 长度区间内收到了 K 个赞。这个解法的代码更短但空间开销较高因为每个 id 都要存一个列表。全局滑窗的空间复杂度更优也更适合延伸理解尺取法所以主推全局滑窗。5. 竞赛实战中的隐藏坑与调试心得5.1 关于D的边界理解为什么是D就缩窗口这个点我反复看到有人问也是出题人最容易埋坑的地方。假设 D10一条记录时间是 1另一条是 11。它们能同时落在一个长度为 10 的时间段里吗如果时间段取 [1,11)长度为 10那 11 就不在里面。取 [1,11]长度是 10严格说闭区间长度要算上右端点一般这类题说的“长度为 D 的时间段”指半开区间或左右闭区间都符合直觉但我们需要按标准统一。蓝桥杯官方给出的理解通常是如果存在某个长度为 D 的区间使得该区间内的点赞数不少于 K 个。那么两个时间戳差值为 D 时是否能被一个长度恰为 D 的区间同时包含比如 D2时间点 1 和 3区间 [1,3] 长度为 2包含 1 和 3。区间 (1,3) 长度为 2不包含两端。区间 [1,3) 长度为 2包含 1 不包含 3。不同定义带来不同答案。为了避免歧义几乎所有已通过的题解都采用“差值小于 D”作为窗口合法条件。也就是说当两个时间点差值等于 D 时我们认定它们不能同时在窗口内需要把左端点右移。为什么因为每条记录代表一个时刻的点事件多个点赞可能发生在同一时刻所有事件发生时刻集合是离散的。一个长度为 D 的闭区间 [L, LD] 在实数轴上包含两个端点但事件是瞬时的它们可能刚好落在端点。不过严格从区间长度定义出发闭区间长度确实是 D包含端点。这时候差值等于 D 的两个时间点应该允许同时存在。但真实的题解为什么用 D 收缩这件事得看题目对时间段的理解。我在当年刷题时也纠结过最后查了蓝桥杯的官方评测数据公认的正确逻辑是时间差严格小于 D。实际上原题叙述里有“任意长度为 D 的时间段”竞赛题默认采用左闭右开的区间表示即 [L, LD)这样区间长度为 D 且不会出现端点归属的争议。按照左闭右开时间差等于 D 时已经处于区间外面了所以必须缩窗口。这个细节直接决定代码里的判断符号写错就是全盘皆输。如果你用的是分组检查连续 K 个赞首尾时间差是否 D同样遵循这个规则。建议做题时直接在注释里写上“左闭右开差值小于D”防止过几天自己看代码犯迷糊。5.2 相同时间戳对窗口的影响如果很多记录都集中在同一个 ts排序后这些记录会紧挨着。窗口扩展时这些同时间的记录会同时被计入它们之间时间差为 0永远不会触发 left 收缩。这正好符合实际同一秒发生 100 个赞它们显然能同时落在一个极短的时间段里所以都应该被统计进去。排序时不需要对相同时间做二次排序因为 id 顺序不影响计数结果。但也有人因为这个踩过坑如果有记录 ts 完全一样且 id 也一样这意味着同一时刻同一个帖子收到了多个赞。注意输入的 N 条记录里 ts 和 id 都可能重复不要把记录当成“每个帖子只出现一次”。我们用 cnt 计数就是为重复情况准备的分组解法里也要把每个时间戳重复加入列表而不能用 set 去重。5.3 输出顺序与重复输出的陷阱输出要求按 id 从小到大输出热帖编号。全局滑窗法标记完 hot 数组后从 1 到 MAXID 遍历输出天然有序。但如果你用 set 存放热帖 id记得最后转成 list 排序再输出否则 set 的无序遍历会直接让你答案格式错乱。重复输出问题也很好理解一个热帖在窗口滑动过程中可能多次满足 cntK每次都会走进 if 分支。如果没有去重标记它会被打印多次。所以布尔数组 hot 的目的不只是排序更是为了去重。有些人会想先收集到 vector 再 unique也可以但没必要。5.4 自测用例与对拍技巧自己在草稿纸上推过的样例不够我建议你至少测下面几组边界数据。第一组单个帖子一个赞判断能否成为热帖1 1 1 1 1N1D1K1只有一个赞窗口时间跨度为 0 小于 Dcnt[1]1K所以输出 1。这里验证了单条记录也能构成热帖。第二组时间差值正好等于 D 的情况2 1 2 1 1 2 1时间差为 1等于 D。按照左闭右开这两个赞不能同时在长度 1 的时间段内所以该帖子不是热帖输出为空。如果你的代码写成了 D 才收缩就会错误地输出 1。这是最容易自测出问题的样例。第三组多 id 混合且时间乱序5 3 2 5 1 1 2 2 2 6 2 10 1排序后为 (1,2),(2,2),(5,1),(6,2),(10,1)。窗口滑动后帖子 2 在时间 1 到 6 之间记录 1,2,6 中前两个时间差 1 小于 3计数 2热帖帖子 1 的记录 5 和 10 时间差 5 大于等于 3不是热帖。最终输出 2。用这个数据反复推演双指针每一步的 cnt 变化对理解帮助很大。还有一个对拍小技巧在本地写一个纯暴力的朴素版本枚举每个帖子、每个可能窗口再用随机器生成小数据比较暴力版本和双指针版本的输出是否完全一致。N 取个位数或两位数多跑几千组随机数据可以快速验证自己的题解在边界条件下没有写歪。我以前准备蓝桥杯时对每道真题都这样对拍尤其是这种几家之言容易混淆的边界定义稍微犹豫就直接跑对拍看结果说话比争论 D 到底是开区间还是闭区间高效多了。5.5 这类题还能怎么延伸理解日志统计之后你会发现它和很多题是一家人求窗口内某一类元素的数量是否达标、求满足条件的最短/最长子数组、以及单调队列优化问题核心都是“维护一个动态窗口快速获取统计值”。比如力扣上的“无重复字符的最长子串”“长度最小的子数组”都是同一套路。蓝桥杯近几年越来越喜欢考这种带有实际场景包装的双指针题把背景剥掉之后算法本质往往很朴素。如果继续深入还可以考虑如果 D 很大、id 很分散如何用离散化来降低数组空间如果要求输出所有贴子中热度最大的 TopK就需要配合堆来做。不过这些属于后话了先把这道 2279 吃透后面遇到类似题会轻松很多。最后再说一句我的实际体会刷真题最大的价值不在于背代码而在于把每一道题为什么会超时、为什么这样优化、边界为什么这么定想清楚。日志统计这题只要亲手手动模拟过几遍窗口收缩过程就再也不会忘记双指针的写法。考场紧张的时候脑中只要能浮现出“左指针收缩、右指针扩展”的动图这道题的分数就到手了。