【数据结构和算法】最近的请求次数

绿毛龟

发布于 2024-01-19 11:42:17

1330

发布于 2024-01-19 11:42:17

文章被收录于专栏：学习道路指南学习道路指南

前言

这是力扣的 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 <= 109
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 104 次

二、题解

2.1 队列问题一般解法

队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作。以下是队列问题的基本算法：

初始化队列：创建一个空队列，并设置一个队头指针和一个队尾指针，分别指向队列的开头和结尾。
入队操作：将一个元素插入到队列的尾部。具体操作是先将队尾指针向后移动一位，然后将新元素插入到队尾指针所指的位置。
出队操作：从队列的头部删除一个元素。具体操作是先将队头指针向后移动一位，然后返回队头指针所指向的元素。如果队列为空，则无法进行出队操作。
获取队头元素：返回队头指针所指向的元素，但不删除该元素。如果队列为空，则无法获取队头元素。
判断队列是否为空：如果队头指针和队尾指针指向同一位置，则队列为空。

以上是队列问题的基本算法，可以用于解决各种相关问题，如生产者消费者问题、约瑟夫环问题等。

2.2 方法一：队列

思路与算法：

由于每次调用 ping 方法时，请求时间 t 是严格单调递增的，因此按照调用顺序存储请求时间可以得到请求时间的严格递增序列。每次调用 ping 方法要求返回过去 3000 毫秒内发生的所有请求数，因此可以将请求时间序列中的距离请求时间超过 3000 毫秒的请求删除，然后计算请求时间序列中的请求数，即为过去 3000 毫秒内发生的所有请求数。

由于最早发生的请求会最先被删除，因此请求时间序列满足先进先出的特点，可以使用队列实现请求时间序列，在构造方法中初始化队列。

对于 ping 方法，首先将过时的请求出队列，如果队列不为空且队首元素距离当前请求时间超过 3000 毫秒，则将队首元素出队列，重复该操作直到队列变为空或者队首元素距离当前请求时间不超过 3000 毫秒。然后将当前请求时间入队列，此时队列内的元素个数即为过去 3000 毫秒内发生的所有请求数，返回队列内的元素个数即可。

三、代码

3.1 方法一：队列

Java版本：

class RecentCounter {

    static final int RANGE = 3000;
    Queue<Integer> queue;

    public RecentCounter() {
        queue=new ArrayDeque<>();
    }

    public int ping(int t) {
        while(!queue.isEmpty()&&t-queue.peek()>RANGE){
            queue.poll();
        }
        queue.add(t);
        return queue.size();
    }
}

C++版本：

#include <queue>
using namespace std;

class RecentCounter {
private:
    static const int RANGE = 3000;
    queue<int> q;

public:
    RecentCounter() {}

    int ping(int t) {
        while (!q.empty() && t - q.front() > RANGE) {
            q.pop();
        }
        q.push(t);
        return q.size();
    }
};

Python版本：

from collections import deque

class RecentCounter:
    RANGE = 3000

    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        while self.q and t - self.q[0] > self.RANGE:
            self.q.popleft()
        self.q.append(t)
        return len(self.q)

Go版本：

package main

import "container/list"

type RecentCounter struct {
    rangeVal int
    q        *list.List
}

func Constructor() RecentCounter {
    return RecentCounter{rangeVal: 3000, q: list.New()}
}

func (this *RecentCounter) Ping(t int) int {
    for this.q.Len() > 0 && t-this.q.Front().Value.(int) > this.rangeVal {
        this.q.Remove(this.q.Front())
    }
    this.q.PushBack(t)
    return this.q.Len()
}

四、复杂度分析

4.1 方法一：队列

时间复杂度：构造方法的时间复杂度是 O(1)，方法 ping 的均摊时间复杂度是 O(1)。每个元素最多入队和出队各一次，因此方法 ping 的均摊时间复杂度是 O(1)。
空间复杂度：O(n)，其中 n 是请求次数。空间复杂度主要取决于队列空间，队列内存储最近 3000毫秒的请求，空间复杂度是 O(n)。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除

队列