Java&C++题解与拓展——leetcode933.最近的请求次数【线段树】

• 题目要求
• 思路一：队列模拟
• • Java
  • C++
  • Rust
• 思路二：线段树
• • Java
  • C++
• 总结

• 维护一个队列，依次放着请求时间，由于每次调用都使用更大的值，所以队首为最早请求；
• 每次压入新的请求，检查头部请求，超时则弹出，然后返回队列大小。

class RecentCounter {
    Queue queue;

    public RecentCounter() {
        queue= new ArrayDeque();
    }
    
    public int ping(int t) {
        queue.offer(t);
        while(queue.peek() < t - 3000)
            queue.poll();
        return queue.size();
    }
}

• 时间复杂度：均摊下来是 O ( 1 ) O(1) O(1)
• 空间复杂度： O ( n ) O(n) O(n)， n n n指队列最长长度

class RecentCounter {
    queue queue;
public:
    RecentCounter() {}
    
    int ping(int t) {
        queue.push(t);
        while(queue.front() < t - 3000)
            queue.pop();
        return queue.size();
    }
};

• 时间复杂度：均摊下来是 O ( 1 ) O(1) O(1)
• 空间复杂度： O ( n ) O(n) O(n)， n n n指队列最长长度

use std::collections::VecDeque;

#[derive(Default)]
struct RecentCounter {
    queue: VecDeque,
}

impl RecentCounter {

    fn new() -> Self {
        RecentCounter::default()
    }
    
    fn ping(&mut self, t: i32) -> i32 {
        self.queue.push_back(t);
        while self.queue.front().unwrap() < &(t - 3000) {
            self.queue.pop_front();
        }
        self.queue.len() as i32
    }
}

• 单点修改+区间查询+强制在线 = 线段树（动态开点）；【之前整理过，这次会用到懒标记】
• 由于不保证插入和查询都是连续的，所以需额外存储左右节点下标 l s ls ls、 r s rs rs，所以 t r e e [ u ] . l s = 0 tree[u].ls=0 tree[u].ls=0和 t r e e [ u ] . r s = 0 tree[u].rs=0 tree[u].rs=0表示子节点未被创建；
• 线段树插入和查询复杂度均为 log ⁡ n log n logn（懒标记确保），因此操作时最多创建数量级 log ⁡ n log n logn的点，空间复杂度为 O ( m log ⁡ n ) O(mlog n) O(mlogn)，而不是 O ( 4 × n ) O(4times n) O(4×n)；
• 这段没看懂就直接引用三叶姐姐题解：

  动态开点相比于原始的线段树实现，本质仍是使用「满二叉树」的形式进行存储，只不过是按需创建区间，如果我们是按照连续段进行查询或插入，最坏情况下仍然会占到 4 × n 4times n 4×n的空间，因此盲猜 log ⁡ n log n logn的常数在 4 4 4左右，保守一点可以直接估算到 6 6 6，因此我们可以估算点数为 6 × m × log ⁡ n 6times mtimeslog n 6×m×logn，其中 n = 1 e 9 n=1e9 n=1e9和 m = 1 e 4 m=1e4 m=1e4分别代表值域大小和查询次数。
  当然一个比较实用的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（ Java 的 128 M 128M 128M可以开到 5 × 1 0 6 5times 10^6 5×106以上）。

【注释少绝不是因为没有认真看懂，绝对不是】

class RecentCounter {
    class Node {
        int ls, rs; // 当前区间的左右子节点下标
        int val; // 当前区间包含请求个数
    }
    int N = (int)1e9, M = 800010, idx = 1;
    Node[] tree = new Node[M];
    void update(int u, int lc, int rc, int x, int v) {
        if(lc == x && rc == x) {
            tree[u].val += (rc - lc + 1) * v;
            return;
        }
        LazyCreate(u);
        int mid = lc + rc >> 1;
        if(x <= mid)
            update(tree[u].ls, lc, mid, x, v);
        else
            update(tree[u].rs, mid + 1, rc, x, v);
        pushup(u);
    }
    int query(int u, int lc, int rc, int l, int r) {
        if(l <= lc && r >= rc)
            return tree[u].val;
        LazyCreate(u);
        int mid = lc + rc >> 1, res = 0;
        if(l <= mid)
            res = query(tree[u].ls, lc, mid, l, r);
        if(r > mid)
            res += query(tree[u].rs, mid + 1, rc, l, r);
        return res;
    }
    void LazyCreate(int u) {
        if(tree[u] == null)
            tree[u] = new Node();
        if(tree[u].ls == 0) {
            tree[u].ls = ++idx;
            tree[tree[u].ls] = new Node();
        }
        if(tree[u].rs == 0) {
            tree[u].rs = ++idx;
            tree[tree[u].rs] = new Node();
        }
    }
    void pushup(int u) {
        tree[u].val = tree[tree[u].ls].val + tree[tree[u].rs].val;
    }

    public RecentCounter() {}
    
    public int ping(int t) {
        update(1, 1, N, t, 1);
        return query(1, 1, N, t - 3000, t);
    }
}

• 时间复杂度：均摊是 O ( log ⁡ n ) O(log n) O(logn)
• 空间复杂度： O ( m log ⁡ n ) O(mlog n) O(mlogn)， m m m为ping的调用次数

【之前写的时候是靠定义一堆变量实现的，这次因为前几天写日志get到了一点定义类的tips，所以定义了类，虽然其实区别也不大啦】

static int N = 1e9, M = 800010;
class RecentCounter {
public:
    class Node {
    public:
        int ls, rs; // 当前区间的左右子节点下标
        int val; // 当前区间包含请求个数
    };
    int idx = 1;
    vector tree = vector (M);

    RecentCounter() {}

    void update(int u, int lc, int rc, int x, int v) {
        if(lc == x && rc == x) {
            tree[u]->val += (rc - lc + 1) * v;
            return;
        }
        LazyCreate(u);
        int mid = (lc + rc) >> 1;
        if(x <= mid)
            update(tree[u]->ls, lc, mid, x, v);
        else
            update(tree[u]->rs, mid + 1, rc, x, v);
        pushup(u);
    }   
    int query(int u, int lc, int rc, int l, int r) {
         if(l <= lc && r >= rc)
            return tree[u]->val;
        LazyCreate(u);
        int mid = (lc + rc) >> 1, res = 0;
        if(l <= mid)
            res = query(tree[u]->ls, lc, mid, l, r);
        if(r > mid)
            res += query(tree[u]->rs, mid + 1, rc, l, r);
        return res;
    } 
    void LazyCreate(int u) {
        if(tree[u] == nullptr)
            tree[u] = new Node();
        if(tree[u]->ls == 0) {
            tree[u]->ls = ++idx;
            tree[tree[u]->ls] = new Node();
        }
        if(tree[u]->rs == 0) {
            tree[u]->rs = ++idx;
            tree[tree[u]->rs] = new Node();
        }
    }
    void pushup(int u) {
        tree[u]->val = tree[tree[u]->ls]->val + tree[tree[u]->rs]->val;
    }

    int ping(int t) {
        update(1, 1, N, t, 1);
        return query(1, 1, N, t - 3000, t);
    }
};

• 时间复杂度：均摊是 O ( log ⁡ n ) O(log n) O(logn)
• 空间复杂度： O ( m log ⁡ n ) O(mlog n) O(mlogn)， m m m为ping的调用次数

快乐模拟做完，回头发现三叶姐姐用了线段树……自从上次学完就没再看过，来用用看看忘得干不干净。

生学Rust的路子看起来有点小问题，还是要先了解点基础知识内容，调用各种和C++有点像的样子。