高频算法面试题 3.队列(Queue)

• 定义：
  特殊的线性表，只能在前端删除，后端插入，先进先出（FIFO—first in first out）线性表。类比排队一样，先排进队列的人先出去。
• 代码实现:

#FIFO: first item we insert will be the first we take out
class Queue:

    #we represent the queue with the help of an array
    def __init__(self):
        self.queue = []
        
    #checks if the queue is empty or not    
    def is_empty(self):
        return self.queue == []
        
    #inserting items 
    def enqueue(self, data):
        self.queue.append(data)
        
    #getting items
    def dequeue(self):
    
        #maybe there is no item in the queue
        if self.is_empty():
            raise Exception("Queue is empty...")
    
        #getting the first item
        data = self.queue[0]
        del self.queue[0]
        return data
        
    #getting the item without removing it
    def peek(self):
        
        #maybe there is no item in the queue
        if self.is_empty():
            raise Exception("Queue is empty...")
    
        return self.queue[0]
    
    #size of the queue
    def size_queue(self):
        return len(self.queue)
    
if __name__ == "__main__":      
    
    queue = Queue()
    
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    
    print(queue.size_queue())
    print("Dequeue: ", queue.dequeue())
    print("Dequeue: ", queue.dequeue())
    print(queue.size_queue())

题目

225和239

leetcode 239

思路
暴力解法: 遍历所有区间,[0,len(nums)-k)], 遍历[x,x+k]窗口得到最大值.
为什么优化解法用到max-heap(堆)呢? 因为窗口每次向右滑动都是减去一个值 加上一个最大值,符合堆的特性.

暴力和O(nlogn)解法

https://realpython.com/modern-web-automation-with-python-and-selenium/

O(n)解法
观察数组中数的性质：
如果窗口中有a,b两数，a在b之前，且a <= b, 那么a不可能为最大值。
如图，注意到窗口中的数是单调递减的

原来的数组

image

按照性质去掉符合的数之后

算法

O(n)解法

实现
*双端队列：双端队列是指允许两端都可以进行入队和出队操作的队列

image.png

class Solution(object):
    
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        from collections import deque
        #定义插入一个数的操作，输入是(时间戳，数字)
        def add(i,num):
            #判断队首是否应该出队
            if len(q) != 0 and q[0][0] == i-k:
                q.popleft()
            #判断队尾是否应该出队
            while (len(q) != 0 and num >= q[-1][1]):
                q.pop()
            #插入新二元组
            q.append((i,num))
            
            #返回队首，即当前最大值
            return q[0][1]
        q = deque()
        
        res = []
        for i,num in enumerate(nums):
            res.append(add(i,num))
        
        #结果只保留k-1往后的，前面的结果都不到k个数
        return res[k-1:]

leetcode相关

1. #225 Implement Stack using Queues
2. #232 Implement Queue using Stacks
3. #239 Sliding Window Maximum
4. #621 Task Scheduler
5. #622 Design Circular Queue