首页 > 其他分享 >单调队列-滑动窗口最大值

单调队列-滑动窗口最大值

时间:2024-07-24 18:39:46浏览次数:8  
标签:窗口 队列 最大值 个数 back 滑动

题目:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
思路:通过双端队列,因为只看得到k个数字,所以先在队列放入k个数字,并且每次放入时都要将他与队列里所拥有的数比较,一直找到第一个大于他的数,小于的全部弹出,这样处理完之后队列的最后一个数就是前k个最大值;再处理后面的数,后面的数同前k个数一样,压入的时候一直找到比他大的数,将小的数全部压出,随后再进行判断,如果队列的最后一个数下标小于等于i-k(数字下标从开始),因为要处理的是连续k个数,所以这种情况代表这个数不在这连续k个数以内,弹出她。

点击查看代码
   deque<int> q;
        vector<int> ans;
        for (int i = 0; i <= k - 1; i++)//先处理先k个数
        {
            while (q.size() && nums[q.back()] <= nums[i])//找到大于他的数,如果没有数了,它就是头,即连续区间最大值
            {
                q.pop_back();//小于他的压出,因为是队列,所以是在队尾压出
            }
            q.push_back(i);
        }
        ans.push_back(nums[q.front()]);
        for (int i = k; i < nums.size(); i++)
        {
            while (q.size() && nums[i] > nums[q.back()])//找到大于他的数,如果没有数了,它就是头,即连续区间最大值
            {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k)//小于等于i-k即代表这个数下标过小,淘汰
            {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }

标签:窗口,队列,最大值,个数,back,滑动
From: https://www.cnblogs.com/tzstlove/p/18321480

相关文章

  • Python 中的工作队列 - 我错过了什么吗?
    这可能会被标记为重复或可能不相关。但我实际上相信这个问题对我和未来缺乏经验的Python开发人员都很重要。由于GIL,用于CPU密集型任务的本地工作队列的概念在Python中至关重要。这方面SE上有明显的答案。使用子进程的方法来绕过缺乏真正的CPU有限并行性的问题。在Pyth......
  • Python 类型暗示​​一个充满 myclass 对象的双端队列
    使用Python3.6或更高版本,我想输入提示一个返回MyClass对象的函数myfunc我如何提示myqueue是一个deque|||充满MyClass对象?objects?fromcollectionsimportdequeglobal_queue=deque()classMyClass:passdefmyfunc(m......
  • Java中的优先级队列(PriorityQueue)(如果想知道Java中有关优先级队列的知识点,那么只看这
        前言:优先级队列(PriorityQueue)是一种抽象数据类型,其中每个元素都关联有一个优先级,元素按照优先级顺序进行处理。✨✨✨这里是秋刀鱼不做梦的BLOG✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客先让我们看一下本文大致的讲解内容:目录1.优......
  • 【数据结构】队列详解和模拟实现
    大家好,今天我们学习队列,本篇博客主要涉及一般队列,环形队列和双端队列,每个队列应用场景均有所差异,下面我们一起来看看吧。队列(Queue)一,概念队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特性入队列:进行插入操作的一端称为队尾(Ta......
  • 单调队列优化DP
    通法:写的时候要灵活变通(可以考虑类似于双指针的技巧,如跳房子)。P3957[NOIP2017普及组]跳房子套个二分,然后由于与位置相关,所以维护一个左端点和右端点,右端点考虑最短步长会不会跳过头,左端点考虑最长步长会不会跳不到。修剪草坪满足连续性质,所以一次考虑一段,\(f_i\)保证\(......
  • 数据结构----队列中的链式队列
     目录 链式队列       1.1逻辑结构:线性结构       1.2存储结构:链式存储      1.3链式队列的操作:                        (1)创建一个空的队列                (2)入列     ......
  • C语言-栈和队列
    文章目录......
  • 单调队列优化 && 斜率优化
    单调队列优化dp浅学1.概念单调队列优化的本质是借助单调性,及时排除不可能的决策,保持候选集合的秩序性。2.例题P1714切蛋糕题目大意:给定一个序列,找出长度不超过\(m\)的连续子序列,使得子序列中所有数的和最大。思路:要求区间和,首先求出前缀和,然后考虑朴素dp,不难想到......
  • 算法——滑动窗口(day7)
    904.水果成篮 904.水果成篮-力扣(LeetCode) 题目解析:根据题意我们可以看出给了我们两个篮子说明我们在开始采摘到结束的过程中只能有两种水果的种类,又要求让我们返回收集水果的最大数目,这不难让我们联想到题目的另一层意思:求最长连续子数组,条件为不超过两种水果种类。......
  • Luogu P4310 绝世好题 题解 [ 绿 ] [ 线性 dp ] [ 单调队列优化 ] [ 二进制优化 ]
    题目:绝世好题。暴力dp显然\(O(n^2)\)转移即可。单调队列优化观察到只有某二进制位两个数都为\(1\)时才能转移,因此我们把每个二进制位开一个单调队列,然后对于一个数\(a\),找到它是\(1\)的二进制位并选其单调队列的队头进行转移,在这之后把这个数加入符合要求的单调队列......