算法长征（7）队列

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 5 分钟

队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

  • 初始化两个栈（s1输入栈、s2输出栈）
  • 将输入栈导出到输出栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class CQueue:
    def __init__(self):
        self.s1 = [] # 输入栈
        self.s2 = [] # 输出栈

    def appendTail(self, value: int) -> None:
        self.s1.append(value)

    def deleteHead(self) -> int:
        if self.s2:
            return self.s2.pop()
        if not self.s1:
            return -1
        while self.s1: # 清空输入栈
            self.s2.append(self.s1.pop())
        return self.s2.pop()

优先队列

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

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

  • 单调队列 0(1) 线性时间算出滑动窗口最大值
  • 优先队列（大根堆） 时间复杂度：O(nlogn) 空间复杂度：O(n) 【注意 Python 默认的优先队列是小根堆】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 单调队列 0(1) 线性时间算出滑动窗口最大值 
        n = len(nums)
        q = collections.deque() # 保存最大索引
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                # 较小的备用,交大的删除前面小的
                q.pop()
            q.append(i)
        ans = [nums[q[0]]] # 第一个窗口初始化
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]:
                # 较小的备用,交大的删除前面小的
                q.pop()
            q.append(i)
            while q[0] <= i-k: # 最大的退役了
                q.popleft()
            ans.append(nums[q[0]])
        return ans
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 优先队列（大根堆） 时间复杂度：O(nlogn) 空间复杂度：O(n)
        n = len(nums)
        # 注意 Python 默认的优先队列是小根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q) #list2最小堆
        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k: # 弹出历史最大值的索引
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类：

  • MovingAverage(int size) 用窗口大小 size 初始化对象。
  • double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MovingAverage:
    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self.nums = deque()
        self.total = 0
        self.size = size
        self.len = 0

    def next(self, val: int) -> float:
        if self.len >= self.size:
            self.total -= self.nums.popleft()
            self.len -= 1
        self.nums.append(val)
        self.total += val
        self.len += 1
        return self.total / self.len

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

请实现 RecentCounter 类：

  • RecentCounter() 初始化计数器，请求数为 0 。

  • int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

  • 优先队列、二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class RecentCounter:
    """
    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        while self.q and (self.q[0] + 3000) < t:
            self.q.popleft()
        self.q.append(t)
        return len(self.q)
    """
    def __init__(self):
        self.ping_list = []

    def ping(self, t: int) -> int:
        self.ping_list.append(t)
        left = bisect_left(self.ping_list, t-3000) 
        return len(self.ping_list) - left

单调队列