题目(hard)

滑动窗口最大值

题解与分析

个人这道题难点在滑动窗口这个思维（怎么实现这个窗口）以及元素的排序，硬排的话时间复杂度太高了，
看的大佬的题解，用单调队列，保证元素在单调队列里面的顺序，
实现上主要靠队列的push和pop，保证顺序是从大到小，在push和pop里面对加入的元素进行判断
比如说：

• push: 每次加入要判断准备加入的元素value和队列末尾的元素的大小（当然本操作的前提是队列要有元素。）如果value大，那么弹出最后一个元素，否则就append进去
• pop:先比较准备删除的元素value和队列首元素的大小，如果相等那么就把原队列第一个元素弹出，至于为什么只判断了等于而没有大于，小于，在下面的代码里面详细介绍了。

class MyQueue: #单调队列（从大到小
    def __init__(self):
        self.queue = [] #使用list来实现单调队列

    #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    #同时pop之前判断队列当前是否为空。
    def pop(self, value):
        print("*******",self.queue)
        if self.queue and self.queue[0]==value:
            # 删除最后一个元素
            self.queue.pop(0)

    #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    #这样就保持了队列里的数值是单调从大到小的了。
    def push(self, value):
        # 先和最后一个元素比较。如果当前值大于最后一个值那么就要把最后一个弹出来
        while self.queue and self.queue[-1]<value:
            self.queue.pop()
        self.queue.append(value)

    #当前队列里的最大值 直接返回队列前端也就是max就可以了。
    def max(self):
        return self.queue[0]

    def travel(self):
        return self.queue

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = MyQueue()
        result = []
        # 这个才是滑动窗口
        # 先把前k个元素添加进quene
        for i in range (k):
            q.push(nums[i])
        result.append(q.max())

        # 这一步是滑动窗口刚刚前进一步，就准备今循环删除最前面不乖的那个元素，有的话就pop
        for i in range (k, len(nums)):
            print(nums[i-k])
            # nums[i-k]就是删除前面的元素，注意是取的nums索引的值！！！！！！！！
            q.pop(nums[i-k])
            print(q.travel())
            q.push(nums[i])
            result.append(q.max())
        return result

# 注意下面代码
# 这一步是滑动窗口刚刚前进一步，就准备今循环删除最前面不乖的那个元素，有的话就pop
        for i in range (k, len(nums)):
            print(nums[i-k])
            # nums[i-k]就是删除前面的元素，注意是取的nums索引的值！！！！！！！！
            q.pop(nums[i-k])
            print(q.travel())
            q.push(nums[i])
            result.append(q.max())