DSA Mastery理论与实验教程

外观

动手实验

Lab 02-E-03：最近请求计数器

使用队列维护递增时间流中的滑动窗口，计算最近 3000 时间单位内的请求数量。

02E0330～45 分钟更新于 2026-08-21DSA Mastery Team基础draft

题目来源：改编自 LeetCode 933：最近的请求次数。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。

学习目标 ​

  • 用队尾接收新请求并从队头淘汰过期请求。
  • 正确处理闭区间左端点 t-3000。
  • 说明每个请求最多入队和出队一次，因此单次操作摊还 O(1)。

前置知识 ​

建议先学习第 2.2 节队列。实现使用 ISO C++17；开始前可运行 make doctor 检查环境。

题目 ​

实现一个“最近请求计数器”。计数器最开始不包含任何请求。

每个请求都带有一个时间戳（timestamp，即用整数表示的请求发生时刻）t。每当收到一个新请求时，都要返回最近 3000 个时间单位内已经收到的请求数量。这里的“最近”包含当前请求，统计范围是闭区间 [t-3000, t]。

输入保证每个新时间戳都严格大于前一个时间戳。因此，请求会按时间先后顺序到达，不需要处理乱序时间戳。

原题把一次请求表示为 ping(t) 调用。本课程一次读入全部时间戳，并依次执行相同的计数过程。

输入格式 ​

  • 第一行：请求数 n；
  • 第二行：n 个严格递增的 64 位整数时间戳 t[0] ... t[n-1]。

输出格式 ​

输出一行 n 个整数。第 i 个整数表示处理时间戳 t[i] 后，闭区间 [t[i]-3000, t[i]] 中的请求总数。

数据范围与限制 ​

项目范围或要求
请求数 n1 ≤ n ≤ 200000
时间戳 t[i]0 ≤ t[i] ≤ 10^15
到达顺序t[i] < t[i+1]
有效窗口闭区间 [t-3000, t]，左右端点都计入
总时间复杂度要求O(n)
额外空间限制最坏 O(n)

样例 ​

input
4
1 100 3001 3002
output
1 2 3 3

样例解释 ​

新请求时间 t当前统计区间区间内的请求时间返回值
1[-2999, 1][1]1
100[-2900, 100][1, 100]2
3001[1, 3001][1, 100, 3001]3
3002[2, 3002][100, 3001, 3002]3

当 t = 3001 时，时间戳 1 恰好位于左端点，因此仍然有效；当 t = 3002 时，统计区间左端点变为 2，时间戳 1 才被移除。

边界与验收重点 ​

  • 恰好位于 t-3000 的请求仍有效。
  • 相邻请求间隔大于 3000 时队列只剩新请求。
  • 使用 64 位时间戳避免大值溢出。

标准输入保证时间戳数量正确且严格递增，无需处理乱序、重复或缺失的时间戳。调试日志必须写入标准错误，标准输出只保留判题结果。

如何验证 ​

powershell
# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录运行：

powershell
pnpm lab:doctor -- labs/chapter-02/exercise/E-02-03-recent-counter
pnpm lab:run -- labs/chapter-02/exercise/E-02-03-recent-counter
pnpm lab:run -- labs/chapter-02/exercise/E-02-03-recent-counter --case 001-sample
pnpm lab:score -- labs/chapter-02/exercise/E-02-03-recent-counter

make run 用于查看各用例；make score 只有得到 100 分才返回成功。样例采用精确输出比较；006-scale 使用两千个密集时间戳，回归窗口持续滑动时的计数更新。线性总复杂度要求仍需结合实现分析判断，不依赖易受机器性能影响的极限超时。

思考与复盘 ​

  1. 为什么淘汰条件是 < t-3000 而不是 ≤ t-3000？
  2. 一次请求中可能弹出很多元素，为什么仍可称为摊还 O(1)？
查看参考答案
  1. 因为统计窗口是闭区间 [t-3000, t]。 时间戳恰好等于 t-3000 时仍位于左端点，必须保留。只有严格小于 t-3000 的请求才已经离开窗口；使用 ≤ 会提前删除仍然有效的左端点请求。
  2. 单次最坏较慢，但整段操作的平均成本是常数。 某次新请求到来时可能连续删除许多旧时间戳，但每个时间戳只会入队一次，也至多被删除一次。处理 n 个请求时，总入队次数为 n，总出队次数不超过 n，所以总时间为 O(n)，平均到每次请求就是摊还 O(1)。

题解 ​

点击查看题解

思路与不变量 ​

时间戳严格递增，因此队列也按时间递增。处理新时间 t 时先把它加入队尾，再从队头删除所有小于 t-3000 的时间戳。

清理结束后，队列恰好保存 [t-3000, t] 内的全部请求，所以队列长度就是答案。

复杂度分析 ​

  • 总时间复杂度：O(n)；每个时间戳只入队一次、至多出队一次；
  • 单次请求摊还 O(1)，最坏单次可能弹出多个旧请求；
  • 额外空间：最坏 O(n)。

边界注意 ​

  • 窗口是闭区间，只有 < t-3000 才过期；
  • 时间戳和减法都应使用 64 位整数；
  • 严格递增保证过期元素只可能出现在队头。
点击查看参考代码
cpp
#include <cstddef>
#include <iostream>
#include <queue>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::size_t n = 0;
    if (!(std::cin >> n)) return 0;

    std::queue<long long> requests;
    for (std::size_t i = 0; i < n; ++i) {
        long long time = 0;
        std::cin >> time;
        requests.push(time);
        while (!requests.empty() && requests.front() < time - 3000) requests.pop();
        if (i > 0) std::cout << ' ';
        std::cout << requests.size();
    }
    std::cout << '\n';
}