【LeetCode】933. 最近的请求次数

携手创作，共同成长！这是我参与「日新计划 8 月更文挑战」的第7天，点击查看活动详情

测试岗位也越来卷了，除了基本的功能测试外，还要有编程基础、脚本经验才脱颖而出。

怎么才能提高我们的编程能力呢，刷LeetCode是最佳的途径之一，话不多数,刷题走起~

一、题目描述：

  • 题目内容

    【LeetCode】933. 最近的请求次数

  • 题目示例

    【LeetCode】933. 最近的请求次数

  • 题目解析

    • 1 <= t <= 109
    • 保证每次对ping调用所使用的t值都严格递增
    • 至多调用ping方法104次

二、思路分析：

我们读取本题，题目要求构建在指定时间段的请求数量，时间段的请求数量是怎么计算呢，我们继续进行审题，对题目中细节进行明确：

  • RecentCounter()初始化计数器，请求数为 0
  • ping()时间段是指时间t在[t-3000,t]中ping请求次数

解答该题，我们可以直接使用数组模拟，求出请求数量，大致思路如下：

  • RecentCounter()初始化，定义数组List来存储请求t时间
  • 遍历List列表中历史的请求时间t与t-3000,prev_ans
  • 请求数量则是len(List)-prev_ans
    【LeetCode】933. 最近的请求次数

按照上述思路，我们使用for循环遍历实现找出小于t-3000的时间，会发现当Ping次数过大时会超时 “`python class RecentCounter(object): def init(self):
self.List = []

    def ping(self, t):
        """
        :type t: int
        :rtype: int
        """
        self.List.append(t)
        prev_ans = 0
        for i in range(len(self.List)):
            if self.List[i] < t-3000:
                prev_ans += 1
            else:
                break
        return len(self.List)-prev_ans
```
64/68case跑不过，上述代码对于遍历会占用太多时间，如下图超时截图：
![image.png](https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/218eca464cd442b6a72f13bbf9e80527~tplv-k3u1fbpfcp-watermark.image?)

根据上述思路，我们可以优化一下，每一次只需查询List中位于列表中第一位进行判断小于t-3000, 无需对整个列表中元素进行遍历，节约查询时间

  • 当self.List[0]小于t-3000时，List.remove(self.List[0])
  • 直到self.List[0]大于等于t-3000时，返回len(self.List)长度就是ping的请求次数
class RecentCounter(object):
    def __init__(self):
        self.List = []
    def ping(self, t):
        """
        :type t: int
        :rtype: int
        """
        self.List.append(t)
        while self.List[0] < t- 3000:
            self.List.remove(self.List[0])
        return len(self.List)

三、总结：

本题考察使用队列只需维护判断List[0]<t-3000的历史时间去除掉，剩下Len(List)就是请求次数，AC记录如下：

【LeetCode】933. 最近的请求次数

  • 时间复杂度：O(1),每个元素至多入队出队各一次
  • 空间复杂度：O(L),其中LL为队列的最大元素个数

以上是本期内容，欢迎大佬们点赞评论，下期见～～～