• 定義：
  特殊的線性表，只能在前端刪除，后端插入，先進(jìn)先出（FIFO—first in first out）線性表。類比排隊(duì)一樣，先排進(jìn)隊(duì)列的人先出去。
• 代碼實(shí)現(xiàn):

#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

思路
暴力解法: 遍歷所有區(qū)間,[0,len(nums)-k)], 遍歷[x,x+k]窗口得到最大值.
為什么優(yōu)化解法用到max-heap(堆)呢? 因?yàn)榇翱诿看蜗蛴一瑒?dòng)都是減去一個(gè)值 加上一個(gè)最大值,符合堆的特性.

暴力和O(nlogn)解法

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

O(n)解法
觀察數(shù)組中數(shù)的性質(zhì)：
如果窗口中有a,b兩數(shù)，a在b之前，且a <= b, 那么a不可能為最大值。
如圖，注意到窗口中的數(shù)是單調(diào)遞減的

原來(lái)的數(shù)組

image

按照性質(zhì)去掉符合的數(shù)之后

算法

O(n)解法

實(shí)現(xiàn)
*雙端隊(duì)列：雙端隊(duì)列是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列

image.png

class Solution(object):
    
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        from collections import deque
        #定義插入一個(gè)數(shù)的操作，輸入是(時(shí)間戳，數(shù)字)
        def add(i,num):
            #判斷隊(duì)首是否應(yīng)該出隊(duì)
            if len(q) != 0 and q[0][0] == i-k:
                q.popleft()
            #判斷隊(duì)尾是否應(yīng)該出隊(duì)
            while (len(q) != 0 and num >= q[-1][1]):
                q.pop()
            #插入新二元組
            q.append((i,num))
            
            #返回隊(duì)首，即當(dāng)前最大值
            return q[0][1]
        q = deque()
        
        res = []
        for i,num in enumerate(nums):
            res.append(add(i,num))
        
        #結(jié)果只保留k-1往后的，前面的結(jié)果都不到k個(gè)數(shù)
        return res[k-1:]

leetcode相關(guān)

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