题目(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())
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:460640 人次
ICP备案号: 辽ICP备20003309号