力扣刷题-队列-滑动窗口最大值

这篇具有很好参考价值的文章主要介绍了力扣刷题-队列-滑动窗口最大值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

239. 滑动窗口最大值

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶:
在线性时间复杂度内解决此题?
力扣刷题-队列-滑动窗口最大值,leetcode刷题,leetcode,算法,python,数据结构

思路-单调队列

参考:https://www.programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html#%E6%80%9D%E8%B7%AF
我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。
这个队列应该长这个样子:

from collections import deque
class MyQueue:
    def __init__(self):
        self.queue = deque()
	def pop(self, value):
        pass
    def push(self, value):
        pass
    def front(self, value):
        pass

每次窗口移动的时候,调用que.pop(滑动窗口中移除元素的数值),que.push(滑动窗口添加元素的数值),然后que.front()就返回我们要的最大值。
然后再分析一下,队列里的元素一定是要排序的,而且要最大值放在出队口,要不然怎么知道最大值呢。
但如果把窗口里的元素都放进队列里,窗口移动的时候,队列需要弹出元素。
那么问题来了,已经排序之后的队列 怎么能把窗口要移除的元素(这个元素可不一定是最大值)弹出呢。
大家此时应该陷入深思…
其实队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以了,同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列,即单调递减或单调递增的队列。目前没有直接支持单调队列,需要我们自己来实现一个单调队列
不要以为实现的单调队列就是 对窗口里面的数进行排序,如果排序的话,那和优先级队列又有什么区别了呢。
来看一下单调队列如何维护队列里的元素。
动画如下:
力扣刷题-队列-滑动窗口最大值,leetcode刷题,leetcode,算法,python,数据结构
对于窗口里的元素{2, 3, 5, 1 ,4},单调队列里只维护{5, 4} 就够了,保持单调队列里单调递减,此时队列出口元素就是窗口里最大元素。
此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢?
设计单调队列的时候,pop,和push操作要保持如下规则:
pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作
push(value):如果push的元素value大于入口元素的数值,那么就将队列入口的元素弹出,直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则,每次窗口移动的时候,只要问que.front()就可以返回当前窗口的最大值。
为了更直观的感受到单调队列的工作过程,以题目示例为例,输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3,动画如下:
力扣刷题-队列-滑动窗口最大值,leetcode刷题,leetcode,算法,python,数据结构
那么我们用什么数据结构来实现这个单调队列呢?
使用deque最为合适(python中也有)
deque用法参考:https://blog.csdn.net/weixin_45666566/article/details/1084409
append、pop、extend默认是右端操作,而appendleft、popleft、extendleft是左端操作。

代码

from collections import deque # 在python中也有双向队列的数据结构
# [0] 和 [-1] 是相对的

class MyQueue: # 单调队列
    def __init__(self):
        self.queue = deque() # 这里需要使用deque实现单调队列 直接使用list会超时
    
    # 每次pop的时候 要判断队列不为空才可以pop 另外只有当出口处的元素等于当前value的时候 才pop
    def pop(self, value):
        if self.queue and self.queue[0] == value: 
            self.queue.popleft() # list.pop()时间复杂度为O(n),这里需要使用collections.deque()
    
    # 在push的时候 如果现在进来的元素要大于队列内的元素 则队列后端的元素就要pop出去 直到现在进来的元素小于队列出口处的元素
    #这样就保持了队列里的数值是单调从大到小的了
    def push(self, value):
        # push前先清理一下队列内的元素
        # 为什么是-1呢 可以画个草图分析 见图1
        while self.queue and value > self.queue[-1]: # deque不为空 且现在进来的元素大于队列出口元素
            self.queue.pop() # 那么此时出口的元素就要pop掉
        self.queue.append(value)

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


class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        que = MyQueue()
        result = [] # 存放结果
        # 前k个元素先入队列
        for i in range(k):
            que.push(nums[i])
        result.append(que.front()) # 前k个元素中的最大值
        # 后面的元素
        for i in range(k, len(nums)):
            que.pop(nums[i-k]) # 每个窗口中最前面的元素要出去
            que.push(nums[i]) # 后面的元素 入队列
            result.append(que.front()) # 将每个窗口中的最大值加入结果
        return result

  • 时间复杂度: O(n)
  • 空间复杂度: O(k)

再来看一下时间复杂度,使用单调队列的时间复杂度是 O(n)。
有的同学可能想了,在队列中 push元素的过程中,还有pop操作呢,感觉不是纯粹的O(n)。
其实,大家可以自己观察一下单调队列的实现,nums 中的每个元素最多也就被 push_back 和 pop_back 各一次,没有任何多余操作,所以整体的复杂度还是 O(n)。
空间复杂度因为我们定义一个辅助队列,所以是O(k)。

扩展

需要要明确的是,题解中单调队列里的pop和push接口,仅适用于本题哈。单调队列不是一成不变的,而是不同场景不同写法,总之要保证队列里单调递减或递增的原则,所以叫做单调队列。 不要以为本题中的单调队列实现就是固定的写法哈。
参考:https://www.programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html文章来源地址https://www.toymoban.com/news/detail-735192.html

到了这里,关于力扣刷题-队列-滑动窗口最大值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法题解】23. 「滑动窗口最大值」单调队列解法

    这是一道 困难 题 题目来自:https://leetcode.cn/problems/sliding-window-maximum/ 给你一个整数数组 nums ,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1: 示

    2023年04月11日
    浏览(53)
  • 【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值

    map|动态规划|单调栈|LeetCode975:奇偶跳 C++算法:滑动窗口总结 单调双向队列 二叉树 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。

    2024年02月04日
    浏览(56)
  • 算法刷题Day 13 滑动窗口最大值+前K个高频元素

    乍一看有点单调栈的意思,但其实不是。 仔细想想应该是用优先队列,似乎也不对,从滑动窗口出来的元素不好从队列中删除 看了随想录之后,是用到单调队列 使用单调队列有坑的地方: case: nums =[-7,-8,7,5,7,1,6,0], k = 4 单调队列在push的时候,如果红框为 = 号,那么结果会出

    2024年02月13日
    浏览(57)
  • 滑动窗口最大值 | 单调队列解题思路与实现,前 K 个高频元素

    学习LeetCode 239与347题目的解题思路与实现方法,包括单调队列与优先级队列(堆)的应用。掌握滑动窗口的最大值与前K个高频元素的解决方案。

    2024年02月13日
    浏览(49)
  • 239. 滑动窗口最大值

    力扣题目链接   (opens new window) 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶: 你能在线性时间复杂度内解决此题吗? 提示:

    2024年02月15日
    浏览(46)
  • 华为OD-滑动窗口最大值

    给你一个整数数组  nums ,有一个大小为  k   的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的  k  个数字。滑动窗口每次只向右移动一位。 返回  滑动窗口中的最大值  。 示例二 代码实现

    2024年02月11日
    浏览(43)
  • leetcode-239-滑动窗口最大值

    题意描述: 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例: 输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动

    2024年02月07日
    浏览(50)
  • LeetCode239.滑动窗口最大值

    看到这道题我就有印象, 我在剑指offer里面做过这道题,我记得当时用的是优先队列,然后我脑子里一下子就有了想法,拿优先队列作为窗口,每往右移动一步,把左边的数remove掉,把右边的数add进来,然后把队头,也就是窗口中最大的元素放入答案数组,然后就写出了如下

    2024年02月11日
    浏览(45)
  • 【LeetCode热题100】【子串】滑动窗口最大值

    题目 给你一个整数数组  nums ,有一个大小为  k   的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的  k  个数字。滑动窗口每次只向右移动一位。 返回  滑动窗口中的最大值  。 示例 1: 示例 2: 提示: 1 = nums.length = 105 -104 = nums[i] = 104 1 =

    2024年01月19日
    浏览(49)
  • LeetCode 239.滑动窗口的最大值 Hot100 单调栈

    给你一个整数数组  nums ,有一个大小为  k   的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的  k  个数字。滑动窗口每次只向右移动一位。 返回  滑动窗口中的最大值  。 示例 1: 示例 2: 提示: 1 = nums.length = 105 -104 = nums[i] = 104 1 = k = num

    2024年02月20日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包