LC 933. 最近的请求次数

题目描述

这是 LeetCode 上的 933. 最近的请求次数 ，难度为简单。

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 $0$ 。
int ping(int t) 在时间 $t$ 添加一个新请求，其中 $t$ 表示以毫秒为单位的某个时间，并返回过去 $3000$ 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 $[t-3000, t]$ 内发生的请求数。

保证每次对 ping 的调用都使用比之前更大的 $t$ 值。

示例 1：

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：

$1 <= t <= 10^9$
保证每次对 ping 调用所使用的 $t$ 值都严格递增
至多调用 ping 方法 $10^4$ 次

以下内容（支持任意的 $[l, r]$ 查询）基于我漏看了 $t$ 递增这一条件。由于 $t$ 递增，因此往前距离大于 $3000$ 的记录无须保留，从而简化了问题，可以使用队列直接做，今天打字很多了，不补充了。

基本分析

根据题意，题目涉及「单点修改」和「区间查询」，根据区间求和问题的总结，可以使用「树状数组」和「线段树」进行求解。

但是留意到 $t$ 的数据范围为 $1e9$，虽然调用次数是 $1e4$，但由于本题是「强制在线」问题，因此我们无法利用「离散化」手段来解决 MLE 问题，而要使用「线段树（动态开点）」来解决。

线段树（动态开点）

动态开点的优势在于，不需要事前构造空树，而是在插入操作 update 和查询操作 query 时根据访问需要进行「开点」操作。由于我们不保证查询和插入都是连续的，因此对于父节点 $u$ 而言，我们不能通过 u << 1 和 u << 1 | 1 的固定方式进行访问，而要将节点 $tr[u]$ 的左右节点所在 tr 数组的下标进行存储，分别记为 ls 和 rs 属性。对于 $tr[u].ls = 0$ 和 $tr[u].rs = 0$ 则是代表子节点尚未被创建，当需要访问到它们，而又尚未创建的时候，则将其进行创建。

线段树的插入和查询都是 $\log{n}$ 的（如果涉及区间修改，则由懒标记来确保 $\log{n}$ 复杂度），因此我们在单次操作的时候，最多会创建数量级为 $\log{n}$ 的点，因此空间复杂度为 $O(m\log{n})$，而不是 $O(4 * n)$，而开点数的预估需不能仅仅根据 $\log{n}$ 来进行，还要对具体常数进行分析，才能得到准确的点数上界。

动态开点相比于原始的线段树实现，本质仍是使用「满二叉树」的形式进行存储，只不过是按需创建区间，如果我们是按照连续段进行查询或插入，最坏情况下仍然会占到 $4 n$ 的空间，因此盲猜 $\log{n}$ 的常数在 $4$ 左右，保守一点可以直接估算到 $6$，因此我们可以估算点数为 $6 m * \log{n}$，其中 $n = 1e9$ 和 $m = 1e4$ 分别代表值域大小和查询次数。

当然一个比较实用的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（ Java 的 $128M$ 可以开到 $5 * 10^6$ 以上）。

代码：

class RecentCounter {
    class Node {
        // ls 和 rs 分别代表当前节点（区间）的左右子节点在 tr 的下标
        // val 代表在当前节点（区间）所包含的数的个数
        int ls, rs, val;
    }
    int N = (int)1e9, M = 800010, idx = 1;
    Node[] tr = new Node[M];
    void update(int u, int lc, int rc, int x, int v) {
        if (lc == x && rc == x) {
            tr[u].val += (rc - lc + 1) * v;
            return ;
        }
        lazyCreate(u);
        int mid = lc + rc >> 1;
        if (x <= mid) update(tr[u].ls, lc, mid, x, v);
        else update(tr[u].rs, mid + 1, rc, x, v);
        pushup(u);
    }
    int query(int u, int lc, int rc, int l, int r) {
        if (l <= lc && rc <= r) return tr[u].val;
        lazyCreate(u);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) ans += query(tr[u].rs, mid + 1, rc, l, r);
        return ans;
    }
    void lazyCreate(int u) {
        if (tr[u] == null) tr[u] = new Node();
        if (tr[u].ls == 0) {
            tr[u].ls = ++idx;
            tr[tr[u].ls] = new Node();
        }
        if (tr[u].rs == 0) {
            tr[u].rs = ++idx;
            tr[tr[u].rs] = new Node();
        }
    }
    void pushup(int u) {
        tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
    }
    public int ping(int t) {
        update(1, 1, N, t, 1);
        return query(1, 1, N, Math.max(0, t - 3000), t);
    }
}

时间复杂度：令 ping 的调用次数为 $m$，值域大小为 $n$，线段树的插入和查询复杂度均为 $O(\log{n})$
空间复杂度：$O(m * \log{n})$

分块

另外一个稍有遗憾的算法是「分块」。

通常来说，值域范围为 $n = 1e9$，我们可以定义块大小为 $\sqrt{n}$，这样时空复杂度都是 $O(\sqrt{n})$。

回到本题，我们定义一个 region 数组，用于存储每个块所包含的数的个数。

对于在位置 $x$ 插入一个值 $v$ 而言，我们可以计算位置 $x$ 所在的块编号 $idx = \left \lfloor \frac{x}{m} \right \rfloor$，然后对块大小进行累加操作（$region[idx] += x$）。同时由于在查询 $[t - 3000, t]$ 时不总是覆盖完整的块（也就是我们可能需要询问某一段的总个数，而这一段仅是块内的部分区间），因此我们需要额外记录位置 $x$ 当前所包含的总数是多少，本题值域大小达到了 $1e9$，因此不能使用静态数组来做，只能使用哈希表来实现动态记录。

我们可以分析单个 ping 操作的计算量/复杂度：

update 操作：$O(1)$；
query 操作：不限制区域大小的话，计算量为 $1e5 * C$（$C$ 是一个小于 $4$ 的常数），由于存在 $[t - 3000, t]$ 的限制，相当于这部分操作全部变成块内了，计算量固定为 $3000$。

于是有通过了所有样例，居然还 TLE 的结果？？？（这是啥测评机制

但经过分析，我们知道瓶颈在于块内操作过多，我们可以利用 $[t - 3000, t]$ 来优化我们的分块算法：直接定义块大小为 $300$，然后倒推出需要多个块空间，分块算法就可以过了（~~特别说明：通过时间为 2022-05-06，未来可能还会有无聊的人来卡分块。~~ 我不信，卡不掉 🤣

代码：

class RecentCounter {
    static int m = 300, n = (int)(1e9 / m) + 10;
    static Map<Integer, Integer> map = new HashMap<>();
    static int[] region = new int[n];
    int getIdx(int x) {
        return x / m;
    }
    void update(int x, int v) {
        map.put(x, map.getOrDefault(x, 0) + v);
        region[getIdx(x)] += v;
    }
    int query(int l, int r) {
        int ans = 0;
        if (getIdx(l) == getIdx(r)) {
            for (int k = l; k <= r; k++) ans += map.getOrDefault(k, 0);
        } else {
            int i = l, j = r;
            while (getIdx(i) == getIdx(l)) ans += map.getOrDefault(i++, 0);
            while (getIdx(j) == getIdx(r)) ans += map.getOrDefault(j--, 0);
            for (int k = getIdx(i); k <= getIdx(j); k++) ans += region[k];
        }
        return ans;
    }
    public RecentCounter() {
        map.clear();
        Arrays.fill(region, 0);
    }
    public int ping(int t) {
        update(t, 1);
        return query(Math.max(0, t - 3000), t);
    }
}

时间复杂度：通常情况下：调用次数为 $m$，值域大小为 $n$，复杂度为 $O(\sqrt{n})$；本题：$O(C)$，其中 $C = 300$ 为块大小
空间复杂度：通常情况下：$O(m +\sqrt{n})$；本题：$O(m + M)$，其中 $M$ 为分块数组大小

最后

这是我们「刷穿 LeetCode」系列文章的第 No.933 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

分块线段树（动态开点）

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 433. 最小基因变化上一篇

LC 713. 乘积小于 K 的子数组下一篇