[英雄星球六月集训LeetCode解题日报] 第16日 队列

一、 933. 最近的请求次数

链接: 933. 最近的请求次数

1. 题目描述

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

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

2. 思路分析

队列模拟即可。
每次插入后把队首所有过远数据出队。
然后返回队长度。

3. 代码实现

class RecentCounter:

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

    def ping(self, t: int) -> int:
        q = self.q
        q.append(t)
        while q[0] < t - 3000:
            q.popleft()
        return len(q)
1
2
3
4
5
6
7
8
9
10
11

二、 1700. 无法吃午餐的学生数量

链接: 1700. 无法吃午餐的学生数量

1. 题目描述

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

2. 思路分析

这题队列模拟是N^2啊，数据规模不大就是了。最好还是计算。

• 先计算学生数量n,两种学生数量分别为a,b.
• 由于学生是循环的，前min(a,b)的三明治一定会被拿光；
• 拿的过程中，不管当前三明治是哪种，只要这种学生没用完，这个三明治一定会被拿走。
• 因此，我们从头开始数，直到当前三明治计数为此种学生总数+1，即学生用光了拿不了这个，
• 那么剩下的三明治就没人能吃。
• 由于三明治是0,1我们可以用一个长度2的数组储存计数，学生同样。

3. 代码实现

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        """
        先计算学生数量n,两种学生数量分别为a,b.
        由于学生是循环的，前min(a,b)的三明治一定会被拿光；
        拿的过程中，不管当前三明治是哪种，只要这种学生没用完，这个三明治一定会被拿走。
        因此，我们从头开始数，直到当前三明治计数为此种学生总数+1，即学生用光了拿不了这个，
        那么剩下的三明治就没人能吃。
        由于三明治是0,1我们可以用一个长度2的数组储存计数，学生同样。
        """
        stu=Counter(students)
        n = len(students)
        san=[0,0]
        for i in range(n):
            s = sandwiches[i]
            san[s] += 1
            if san[s] == stu[s]+1:
                return n - i                
        return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、 2073. 买票需要的时间

链接: 2073. 买票需要的时间

1. 题目描述

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

2. 思路分析

这题也不用队列模拟，直接计算很好想。
把k买完之前的人买票总时间加起来即可。
位于前边的人消耗的时间不会超过k本人，因为k买到就走了；位于后边的人同样不会，而且比k少一轮。

3. 代码实现

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        """第k个人要买a张票，
        我们分析排在他前边的人，要买b张票，
            如果b<=a，那么这些人花的时间就是b。
            如果b>a,那么这些人花了a之后，k就买到了，也就不计数。
            因此这些人花的时间是min(tickets[i], a)
        排在他后边的人类似，但是当k自己买到后，当前队列也不需要计算了
            因此是min(tickets[i], a-1)
        """
        a = tickets[k]
        s = 0
        for i in range(k+1):
            s += min(tickets[i], a)
        
        for i in range(k+1,len(tickets)):
            s += min(tickets[i], a-1)
        return s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四、239. 滑动窗口最大值

链接: 239. 滑动窗口最大值

1. 题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

2. 思路分析

单调队列模板题。参考我的[python刷题模板] 单调队列。
滑窗右移时，新数x入队，把队尾所有小于x的数据全弹出丢弃，这些数据对后续滑窗的贡献不会超过x。
然后判断一下队首是否出窗需要弹出，剩下的队首就是答案。

3. 代码实现

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """单调队列模板
        维护单调递减队列，
        入队时，把队尾小于本数的全干掉，这些数对后续窗口的贡献不会超过本数。
        判断队首距离当前超过k则弹出，剩下的队首就是答案。        
        """
        q = deque()
        for i in range(k):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
        ans = []
        ans.append(nums[q[0]])
        for i in range(k,len(nums)):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
            if q[0] <= i-k:
                q.popleft()
            ans.append(nums[q[0]])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

五、参考链接

• [python刷题模板] 单调队列。