933. 最近的请求次数

大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

让我们实现一个 RecentCounter 类来计算时间窗口为 [t - 3000, t] 之间的请求个数。

可能有些同学看不懂题目，我详细解释一下：

题目的第一个示例为例：

["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

它的含义是，第一行是调用的函数名，第二行是函数的参数，即：

1. 调用 RecentCounter()，没有输入值，表示初始化计数器，时间为 0，记数为 0
2. 调用 ping()，输入值是 1，即查询窗口在 [-2999, 1] 之间有多少 ping
3. 调用 ping()，输入值是 100，即查询窗口在 [-2900, 100] 之间有多少 ping
4. 调用 ping()，输入值是 3001，即查询窗口在 [1, 3001] 之间有多少 ping
5. 调用 ping()，输入值是 3002，即查询窗口在 [2, 3002] 之间有多少 ping

它的调用的可视化如下图所示：

解题方法

从上面的图可以看出，我们其实是在用一个大小为 的滑动窗口，在统计窗口内有多少个 ping。

因此，可以用固定时间窗口为 3000 的队列来模拟，每次 ping(t)的时候，把队列头部已经超过 的所有请求去除。然后看队列中多少元素，就是 之间的请求数。这是大部分题解采用的方法。

我换了一个方法，不使用队列进行模拟。

我使用一个数组，保存所有的请求时间 $t$；当新请求到达时，我使用二分查找大于等于 $t - 3000$ 的第一个位置。因此就可以获得 之间的数字个数。

举个例子：

为什么可以用二分查找呢？

因为题目已经保证了每次调用 ping(t)的时候， 都是增加的，也就是说如果我们把所有的 t 保存到数组中，那么数组是单调递增的有序数组。另外，二分查找的时间复杂度是 ，题目给出的数据范围是最多调用 ping()方法 次，因此总的时间复杂度应该是 $O(N * log(N))$，不会超过力扣所限制的 的计算量。

因此可以使用二分查找。

注意我们在数组中查询的不是确切的一个值，而是 的值，注意下面代码中的对普通二分查找的改变。

代码如下：

class RecentCounter:
    def __init__(self):
        self.nums = []
    def ping(self, t):
        """
        :type t: int
        :rtype: int
        """
        self.nums.append(t)
        cur_pos = len(self.nums)
        prev_pos = bisect.bisect_left(self.nums, t - 3000)
        return cur_pos - prev_pos
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

class RecentCounter {
public:
    RecentCounter() {
    }
    int ping(int t) {
        requests.push_back(t);
        int prev = bisectLeft(requests, t - 3000);
        return requests.size() - prev;
    }
    int bisectLeft(vector<int>& requests, int target) {
        int left = 0;
        int right = requests.size();
        // [left, right)
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (requests[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
private:
    vector<int> requests;
};
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

class RecentCounter {
    ArrayList<Integer> requests;
    public RecentCounter() {
        requests = new ArrayList<>();
    }
    public int ping(int t) {
        requests.add(t);
        int prev = bisectLeft(requests, t - 3000);
        return requests.size() - prev;
    }
    public int bisectLeft(ArrayList<Integer> requests, int target) {
        int left = 0;
        int right = requests.size();
        // [left, right)
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (requests.get(mid) >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter obj = new RecentCounter();
 * int param_1 = obj.ping(t);
 */

复杂度

• 时间复杂度：$O(N * log(N))$
• 空间复杂度：$O(N)$

  总结

1. 力扣的 Easy 和 Medium 题目一般只考一个知识点，活学活用哇~

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。