企业官网建设流程全解析

日志统计这道题，蓝桥杯第九届省赛的经典题目，OJ编号2279，我在备赛期间反复刷过好几遍，也在赛场上见过不少同学在这里丢分。题目本身不复杂，数据范围却卡得恰到好处——把一批只会暴力枚举的人挡在门外。今天就把这题从读题到代码实现完整拆开讲一遍，包括常见的边界坑、排序细节、双指针写法，以及三种主流语言的实现差异，希望能帮还在刷真题的人彻底吃透它。

1. 题目2279到底在说什么：日志统计的题面与核心矛盾

1.1 题面原貌与输入输出规则

先还原一下题目描述。小明维护着一个程序员论坛，论坛有 N 条点赞记录，每条记录包含两个整数：时间 ts 和帖子编号 id，表示编号为 id 的帖子在 ts 时刻收到了一次点赞。现在小明想知道哪些帖子曾经是“热帖”，判断标准是：如果存在一个任意长度为 D 的时间段，在这个时间段内某个帖子收到的赞数不少于 K 个，那么它就是热帖。要求按 id 从小到大输出所有热帖的编号，每个 id 占一行。

输入格式不复杂，第一行是三个整数 N、D、K，接下来 N 行每行两个整数 ts 和 id。数据范围我记得很清楚：N、D、K 都能到 100000，ts 和 id 也都在 1 到 100000 区间内。这意味着什么？O(N乘D) 的复杂度一定超时，O(N^2) 的复杂度更是想都不要想。题目给的限制有意引导你往线性或 O(N log N) 的思路上靠。

1.2 表面是一道模拟题，本质是滑动窗口

很多第一次做这题的人会陷入一种直觉：枚举每个时间段的起点，再统计该时间窗口内的所有记录。这个思路看起来没毛病，但一旦 N 是十万，D 是十万，你就算枚举每个帖子、每个可能的时间窗口，总计算量轻松超过十的十次方。比赛环境根本不可能放你过去。

这题真正的考察点在于：日志记录本质上是按时间先后顺序发生的。如果我们把 N 条记录按时间排序，那么“任意长度为 D 的时间段”就变成了排序后一维坐标轴上的一个区间。维护这个区间里各个 id 的点赞次数，区间右端点每次扩展一条记录，左端点根据时间差不断收缩，整个过程只需要每条记录进出窗口一次。这就是经典的滑动窗口双指针思路，和单调队列、尺取法的本质是一脉相承的。

理解了这个核心矛盾，题目就成功了一大半。下面从复杂度开始认真推导。

2. 暴力做法为什么必挂：从N=1e5看时间复杂度的生死线

2.1 最常见的错误思路：按时间段枚举加统计

拿到题目，第一反应通常是：枚举每个时间段起点 L，终点 L+D，然后扫一遍所有记录，统计在时间区间内的每个 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 计数减 1，left 指针右移。这个过程不断重复，直到时间跨度重新小于 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); vector<Log> 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; vector<int> cnt(MAXID + 1, 0); vector<bool> 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，不会越界，因为 right==left 时时间差恒为 0，肯定小于 D（D 为正整数）。
• 标记热帖放在收缩之后，确保检查的一定是合法窗口。注意当前记录的 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(key=lambda 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 的性能主要耗在排序和循环上，N=1e5 完全可控，但如果你的环境里 Python 循环过慢，可以考虑用数组模拟指针。还有一个 Python 特有的坑：tuple 比较会先比 ts 再比 id，我们 sort 不指定 key 其实也能得到按时间排序的结果，但显式 key=lambda x: x[0] 更清晰。用 sys.stdin.buffer.read() 一次性读取，比逐行 input() 快很多，这是我实测在蓝桥云课这种环境下能把运行时间压进一秒钟的关键。

需要说明的是，以上三种写法都是基于全局滑动窗口。还有一种常见的按帖子分组解法：把每个 id 的点赞时间单独存一个列表，每个列表排序后，检查连续 K 个点赞的首尾时间差是否小于 D，如果小于说明该帖子在某个 D 长度区间内收到了 K 个赞。这个解法的代码更短，但空间开销较高，因为每个 id 都要存一个列表。全局滑窗的空间复杂度更优，也更适合延伸理解尺取法，所以主推全局滑窗。

5. 竞赛实战中的隐藏坑与调试心得

5.1 关于D的边界理解：为什么是>=D就缩窗口

这个点我反复看到有人问，也是出题人最容易埋坑的地方。假设 D=10，一条记录时间是 1，另一条是 11。它们能同时落在一个长度为 10 的时间段里吗？如果时间段取 [1,11)，长度为 10，那 11 就不在里面。取 [1,11]，长度是 10？严格说闭区间长度要算上右端点，一般这类题说的“长度为 D 的时间段”指半开区间或左右闭区间都符合直觉，但我们需要按标准统一。

蓝桥杯官方给出的理解通常是：如果存在某个长度为 D 的区间，使得该区间内的点赞数不少于 K 个。那么两个时间戳差值为 D 时，是否能被一个长度恰为 D 的区间同时包含？比如 D=2，时间点 1 和 3，区间 [1,3] 长度为 2，包含 1 和 3。区间 (1,3) 长度为 2，不包含两端。区间 [1,3) 长度为 2，包含 1 不包含 3。不同定义带来不同答案。

为了避免歧义，几乎所有已通过的题解都采用“差值小于 D”作为窗口合法条件。也就是说，当两个时间点差值等于 D 时，我们认定它们不能同时在窗口内，需要把左端点右移。为什么？因为每条记录代表一个时刻的点事件，多个点赞可能发生在同一时刻，所有事件发生时刻集合是离散的。一个长度为 D 的闭区间 [L, L+D] 在实数轴上包含两个端点，但事件是瞬时的，它们可能刚好落在端点。不过严格从区间长度定义出发，闭区间长度确实是 D，包含端点。这时候差值等于 D 的两个时间点应该允许同时存在。

但真实的题解为什么用 >= D 收缩？这件事得看题目对时间段的理解。我在当年刷题时也纠结过，最后查了蓝桥杯的官方评测数据，公认的正确逻辑是：时间差严格小于 D。实际上原题叙述里有“任意长度为 D 的时间段”，竞赛题默认采用左闭右开的区间表示，即 [L, L+D)，这样区间长度为 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 的无序遍历会直接让你答案格式错乱。

重复输出问题也很好理解：一个热帖在窗口滑动过程中可能多次满足 cnt>=K，每次都会走进 if 分支。如果没有去重标记，它会被打印多次。所以布尔数组 hot 的目的不只是排序，更是为了去重。有些人会想先收集到 vector 再 unique，也可以，但没必要。

5.4 自测用例与对拍技巧

自己在草稿纸上推过的样例不够，我建议你至少测下面几组边界数据。

第一组，单个帖子一个赞，判断能否成为热帖：

1 1 1 1 1

N=1，D=1，K=1，只有一个赞，窗口时间跨度为 0 小于 D，cnt[1]=1>=K，所以输出 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 吃透，后面遇到类似题会轻松很多。

最后再说一句我的实际体会：刷真题最大的价值不在于背代码，而在于把每一道题为什么会超时、为什么这样优化、边界为什么这么定想清楚。日志统计这题，只要亲手手动模拟过几遍窗口收缩过程，就再也不会忘记双指针的写法。考场紧张的时候，脑中只要能浮现出“左指针收缩、右指针扩展”的动图，这道题的分数就到手了。