1. 题目解读与背景分析1.1 题目到底是什么第一次看到“日志统计”这四个字可能不少朋友会觉得这题很简单——无非就是给一堆日志统计统计热度呗。但真正上手之后才发现这道2018年蓝桥杯第九届的真题实际上是考察滑动窗口、双指针、排序哈希综合运用的经典题目也是当年区分度比较高的一道题。先看原题大致描述小明维护着一个程序员论坛收集了一份“点赞”日志日志共有N行每行包含两个整数分别表示ts时间戳和id帖子编号。现在小明想知道在哪些帖子中任意长度为D的时间段内注意是长度为D不是差值为D收到的点赞数不少于K个。如果满足这个条件则称该帖为“热帖”。要求输出所有热帖的id并按从小到大排序。这个题目在蓝桥杯历年真题里地位很特殊。它不像纯模拟题那样无脑也不像图论、DP那样需要高深算法恰恰卡在一个“需要一点优化思维但又不至于太难”的位置。对于备赛蓝桥杯的同学来说这道题是练习滑动窗口思想的绝佳素材特别是准备蓝桥杯python组、Java组、C组的同学几乎都绕不开它。1.2 题目考察的核心能力这道题表面上考察的是模拟统计实际上暗含三个核心能力的考察第一个是数据组织能力。输入的日志是无序的时间戳和帖子id交错在一起怎么把数据组织成方便处理的结构这决定了后续算法的复杂度。第二个是时间复杂度的敏感度。如果直接对每个帖子、每个时间区间暴力枚举数据量一大必然超时。很多同学第一次写出来的暴力版本在小数据上没问题一到蓝桥杯的评测数据就直接时间超限。今年不少同学在蓝桥杯赛场上栽跟头往往不是不会做而是没意识到需要优化。第三个是边界条件的处理能力。时间区间是左闭右开还是左闭右闭点赞数“不少于K”还是“大于K”排序去重的细节这些看似小的点却直接决定代码能否AC。这道题放在第九届是有一定“劝退”作用的但现在回头看它其实就是滑动窗口的入门经典。掌握了这道题后面遇到同类区间统计问题就会有很清晰的思路。2. 核心思路拆解与方案选型2.1 为什么不能暴力解很多人的第一反应是直接用一个二维数组cnt[postId][time]然后对于每个帖子枚举所有长度为D的时间窗口统计点赞数。理论上看起来没啥问题但算一下复杂度就明白了。假设N条日志帖子编号最大值是M时间戳最大值是T暴力做法的时间复杂度是O(N * T)或者O(M * T)在数据范围较大的情况下比如N达到10^5时间戳达到10^5甚至更大这个复杂度是无法承受的。蓝桥杯的评测虽然不像ACM那么变态但对超时同样是零容忍。还有一个隐藏问题日志数据是稀疏的。并不是每个时间点都有点赞记录用一个稠密的二维数组去存储稀疏的数据本身就是极大浪费。这也是为什么需要哈希表来组织数据。2.2 滑动窗口这道题最优雅的解法既然暴力不行那就要换个思路。这里我直接给出核心观察对于一个固定的帖子id它的点赞时间戳排好序之后我们只需要判断是否存在一个区间[i, j]使得times[j] - times[i] D且区间内点赞数即j-i1不小于K。这里有个关键细节题目说的是“长度为D的时间段”在代码实现时通常判断times[j] - times[i] D这样可以保证窗口长度严格小于D。不过要注意不同版本的题目描述可能有差异有的版本是 D这个细节决定了边界条件怎么写。具体步骤是这样的用哈希表字典把每个帖子id对应的所有点赞时间戳存起来每个id的时间戳是一个列表。对每个id的时间戳列表从小到大排序。在每个排序后的列表上用双指针维护一个窗口右指针不断向右扩展把新的时间戳纳入窗口当times[right] - times[left] D时左指针向右收缩直到窗口合法。如果窗口内的元素个数点赞数达到K则该id就是热帖记录答案。这个思路的时间复杂度是O(N log N)主要开销在排序上双指针部分每个元素最多进出窗口一次是线性的。排序加双指针的组合直接就把原来的超高复杂度降下来了。2.3 哈希表选择C map还是unordered_map如果使用C实现这里有个很实际的选择题用mapint, vectorint还是unordered_mapint, vectorintmap底层是红黑树key有序但插入和查询是O(log N)。unordered_map底层是哈希表插入和查询均摊O(1)但key无序。因为最后要按照id从小到大输出热帖用map的话遍历时天然有序省去最后排序的一步用unordered_map则需要在结尾单独排序。从代码简洁角度看map更省事而且N在10^5量级时两者的性能差距并不明显。不过如果追求极致性能且不介意多写一行排序unordered_map在数据量大的时候会略快一些。我个人在实际写题时通常用map因为蓝桥杯的评测环境对代码长度和出错概率更敏感map少一个排序步骤更稳。用Python的话就不存在这个问题了直接字典搞定。3. 完整实现与代码深度解析3.1 C完整实现先上我用C写的完整AC代码代码里加了详细注释方便对照分析#include bits/stdc.h using namespace std; int main() { int n, d, k; scanf(%d %d %d, n, d, k); mapint, vectorint mp; // id - 时间戳列表 for (int i 0; i n; i) { int ts, id; scanf(%d %d, ts, id); mp[id].push_back(ts); } vectorint ans; for (auto it : mp) { int id it.first; vectorint times it.second; sort(times.begin(), times.end()); int left 0, right 0; int cnt 0; // 滑动窗口窗口内是 [left, right) while (right (int)times.size()) { // 窗口右边界扩展纳入一个新时间戳 while (right (int)times.size() times[right] - times[left] d) { cnt; right; } // 如果当前窗口内点赞数满足条件记录答案 if (cnt k) { ans.push_back(id); break; // 找到一个即可不需要继续找 } // 左边界收缩移出一个时间戳 cnt--; left; // 注意这里如果right left需要重置窗口 if (left right) { cnt 0; if (right (int)times.size()) { cnt; right; } } } } for (int id : ans) { printf(%d\n, id); } return 0; }这段代码用的是mapint, vectorint天然按id排序最后直接遍历输出即可。但这段代码有个细节要仔细想当left移动之后cnt维护的是当前窗口[left, right)内的元素个数而不是简单的right - left因为right可能已经移动到了末尾而cnt的变化需要手动维护。其实这里有一个更简洁的写法伪代码如下for (auto it : mp) { sort(it.second.begin(), it.second.end()); int l 0, r 0; while (r it.second.size()) { if (it.second[r] - it.second[l] d) { r; } else { l; } if (r - l k) { ans.push_back(it.first); break; } } }这个写法更直观先用l和r两个指针维护窗口当窗口不满足时间差小于d时左指针右移当窗口满足时间差小于d时右指针右移每次移动后检查窗口长度r - l是否达到k。窗口长度就是点赞数因为窗口内每个时间戳代表一次点赞。注意这个写法里r - l恰好等于窗口内元素数量不需要额外维护cnt逻辑更清晰。这也是我推荐大家掌握的版本。3.2 Python完整实现Python版本对准备蓝桥杯python组的同学更重要因为近年来Python参赛人数暴涨这道题也频繁出现在各路真题解析里。Python实现如下n, d, k map(int, input().split()) from collections import defaultdict mp defaultdict(list) for _ in range(n): ts, id_ map(int, input().split()) mp[id_].append(ts) ans [] for id_ in sorted(mp.keys()): times sorted(mp[id_]) l 0 for r in range(len(times)): # 保证窗口内时间差小于 d while times[r] - times[l] d: l 1 # 如果窗口长度达到 k说明是热帖 if r - l 1 k: ans.append(id_) break for id_ in ans: print(id_)Python版本的逻辑更紧凑外层遍历mp的key即帖子id按id排序后依次处理。内层用for r in range(len(times))作为右指针每次循环中当窗口不满足时间差小于d时左指针l右移直到窗口重新合法。然后判断r-l1是否达到k。这里有一个关键点为什么只判断一次就break因为只要存在一个满足条件的窗口该帖子就是热帖不需要继续找。这个优化可以节省大量时间。3.3 参数计算与核心细节说明这道题的“参数”主要体现在时间差判断上。题目描述说“任意长度为D的时间段”但代码里是times[r] - times[l] d。为什么是小于而不是小于等于这里涉及到时间段的定义如果时间段是从t到tD那么长度是D但点赞时刻如果在tD这一瞬间算不算在这个时间段内不同题目描述有细微差别。蓝桥杯2018年第九届这题的官方说法是“长度为D的时间段”通常理解为开区间即times[r] - times[l] d。但有一版这道题的描述写的是“在任意长度为D的闭区间内”那判断条件就应该是times[r] - times[l] d。这就要求我们读题时格外注意比赛时碰到这种边界描述一定要仔细。我在备考时喜欢把两种判断都写一遍本地验证边界数据后再提交这样最稳。另外窗口内的时间戳数量就是点赞次数因为同一个时间戳可能出现多次这里要特别说明在真实的日志统计数据中一个时间戳不可能对应同一条帖子两次点赞但蓝桥杯的测试数据里同一时间戳同一条帖子可能出现多次理论上不合理但数据就是这样给的。vector里每个元素代表一次点赞两个相同的时间戳也代表两次点赞所以r-l1就是点赞数不做去重。这一点很多新手会踩坑把时间戳去重后再统计反而错了。3.4 两种思路对比总结方案时间复杂度空间复杂度实现难度推荐指数暴力枚举帖子id × 时间窗口O(N * T)O(N)低不推荐排序 双指针滑动窗口O(N log N)O(N)中强烈推荐排序 前缀和O(N log N M * D)O(N)中看情况前缀和方案也是一种可行思路对每个帖子id的时间戳做前缀和然后枚举每个长度为D的窗口用前缀和O(1)查询窗口内点赞数。但这种方式需要把时间戳离散化或者映射到连续数组代码复杂度比双指针高而且枚举所有窗口的效率反而不如双指针一步到位。所以主流解法还是滑动窗口。4. 常见问题与排查技巧实录4.1 超时问题十有八九是暴力了这是最常见的错误。你在本地测试小数据时一切正常交到OJ上就TLE。原因就是复杂度太高。解决办法只有一个换滑动窗口。如果已经用了滑动窗口还超时可以检查以下几点是不是用了vector的push_back频繁扩容可以预先reserve或换成deque。是不是在循环里反复调用size()函数在C里times.size()返回的是size_t循环里反复调用效率略低可以提前存起来。是不是用了endl进行输出大数据的输出应该用\n而不是endl。4.2 边界条件错误最常见的边界错误是用times[r] - times[l] d但题目要求开区间导致边界情况多算了一个。窗口内点赞数判断是 k还是 k题面要求“不少于K个”必然是 k。热帖id要从大到小还是从小到大题目要求从小到大。判断边界最有效的方法是构造一组极端小数据手算一遍。比如输入 5 2 2 1 1 2 1 3 1 4 2 5 2手动模拟帖子1的时间戳是1、2、3d2区间[1,3)包含1和2点赞数2达到k2所以1是热帖。帖子2的时间戳是4、5区间[4,6)包含4和5点赞数2也是热帖。输出应该是1和2。用这组数据验证代码逻辑边界基本能暴露出来。4.3 数据去重的误区前面提到一定不要对同一帖子的时间戳去重。逻辑上听起来好像同一条帖子同一秒只能被点赞一次但题意没有做这个限制而且蓝桥杯的评测数据并不会遵守这种“物理直觉”。你一旦去重那些“同一秒被点赞两次”的数据点就会漏判。用一个极端例子说明假设d1k2某帖子的时间戳列表是[1, 1]这代表在时间1有两次点赞。按照题意在长度为1的时间段[1,2)内点赞数为2是热帖。如果去重后只剩[1]点赞数为1就错误地判定为非热帖。这种隐蔽的坑只有亲手踩过才会记住。4.4 输出格式与排序蓝桥杯的判题对输出格式要求严格每个id占一行末尾不能有多余空格最后一行也无所谓换不换行。如果用map遍历天然有序用unordered_map则要最后sort一下。有些同学直接在遍历unordered_map时输出结果顺序错误白丢分。还有一个细节空输出。如果没有任何热帖是输出空还是输出什么题目没说有特殊输出那就什么都不输出。有些同学会在最后加一个换行虽然一般不会判错但稳妥起见没有答案就直接结束不要画蛇添足。4.5 读入速度优化对于C选手如果担心cin太慢最直接的办法是用scanf。但如果你想用cin可以加上这两行ios::sync_with_stdio(false); cin.tie(0);这两行能显著提升cin的读取速度。注意加了ios::sync_with_stdio(false)之后就不能再混用scanf和cin了否则容易出错。Python选手则用sys.stdin.buffer.read()做快速读入可以大幅提高大数据下的读入效率import sys data sys.stdin.buffer.read().split() n, d, k map(int, data[:3]) idx 3 for _ in range(n): ts int(data[idx]); id_ int(data[idx1]); idx 2 mp[id_].append(ts)4.6 常见问题速查表现象原因解决方式本地运行正常OJ上超时暴力枚举或低效输出改用滑动窗口用\n输出答案错误差1个结果边界条件判断出错检查 d还是 d k还是 k输出id顺序不对用unordered_map未排序改用map或最后sort漏掉一些热帖把同一帖子的时间戳去重保留重复时间戳不去重数组越界双指针移动时左指针超过右指针在循环内加l r保护判断代码复杂难调窗口维护逻辑太啰嗦用简洁写法右指针for循环左指针while收缩5. 同类题目扩展与进阶思路5.1 滑动窗口应用的场景延伸“日志统计”本质上是一个固定长度区间内的计数问题。这类问题在算法竞赛里出现频率极高常见变体包括长度为D的窗口内最大点赞数是多少不要求到K而是求最大值多个帖子竞争热度求最热帖子id就是边维护边更新最大值时间区间是环形的时间戳是一个环需要考虑首尾相接的情况点赞数带上权重每个人可以点赞多次权重可能是非线性的这些变体在蓝桥杯后续的年份里都有影子。比如第十四届的某些模拟题、计数题底层思路都和这道题一脉相承。掌握了滑动窗口相当于拿到了区间统计问题的通用钥匙。5.2 从滑动窗口到双指针的其他考法双指针不只是滑动窗口的别名它还衍生出很多变种对撞指针有序数组两数之和、快慢指针链表判环、同向双指针区间最值、去重。在蓝桥杯中双指针的结合场景很常见比如“日志统计”这种“先排序再双指针”的模式在很多真题里反复出现。我建议备赛的同学把这道题刷透之后主动做几道类似的题加深印象比如POJ上的某些区间统计题、LeetCode的“无重复字符的最长子串”“长度最小的子数组”等。这些题的底层框架高度相似都是“右指针扩展 左指针收缩”区别只在于收缩条件和答案更新时机。5.3 如果数据规模再扩大怎么办如果这道题的N扩大到10^6甚至更大O(N log N)的排序可能成为瓶颈。这时候可以考虑把时间戳的统计换成“桶排序”思想由于时间戳范围有限比如最大是10^5可以用计数数组直接记录每个时间点是否有点赞再做前缀和。但这样做的前提是提前知道时间戳的最大范围否则空间可能不够。还有一种思路是用“对偶尺取”或者其他更高级的算法但蓝桥杯一般不会考到这么深。目前这道题的数据范围排序双指针是绝对够用的。5.4 考场实战建议在2026年蓝桥杯备考中这道题很适合作为“模拟数据结构”模块的重点练习。我给大家几个实战层面的建议拿到题先看数据范围不要急着写代码。如果N在10^5量级任何O(N^2)的做法都不可取直接往滑动窗口上思考。代码写完先构造边界测试比如K1、D1、所有点赞集中在同一秒这类极端情况确认无误再提交。蓝桥杯的评测是赛后统一判分没有实时反馈所以必须靠平时的扎实积累来保证一遍AC。6. 实操总结与个人经验记录这道“日志统计”我刷了不止一遍不同时期的收获完全不同。第一次做的时候也是一通暴力结果在时间测试点上翻车。第二次静下来分析数据特征才想到排序双指针。到第三遍做的时候已经能几分钟内写出完全正确的代码连注释都不用加。其中有一个细节印象特别深刻我当时用了unordered_map但忘了最后排序结果输出的热帖顺序是乱的。界面上显示答案错误我看了很久都没发现问题最后对比官方输出才恍然大悟。从那时起我养成了一个习惯——凡是最后要求按顺序输出的题目优先用map如果用了unordered_map一定在末尾补上sort。还有一个体会是这种区间计数问题最怕的不是算法不会而是边界条件不清。建议大家在做这类题的时候把“区间开闭”“不少于”这些描述专门圈出来转化为代码中的具体符号。我的习惯是先在草稿纸上写“开区间 d点赞数 k”再动键盘这样能大幅减少低级错误。最后再分享一个小技巧如果题目数据很弱N很小暴力写起来快但千万不要养成依赖暴力的习惯。蓝桥杯近几年的题目数据范围逐年增大以前暴力能过的题现在可能就过不了。把滑动窗口这种基础算法练成肌肉记忆才是考场上的真正保障。这道题虽然只是众多蓝桥杯真题中的一道但它的价值在于用最朴素的方式展示了“如何从暴力思维过渡到优化思维”。这也是我在备赛过程中最看重的收获。