首页 > 其他分享 >【队列】力扣239:滑动窗口最大值

【队列】力扣239:滑动窗口最大值

时间:2022-08-20 20:34:56浏览次数:72  
标签:窗口 队列 双端 最大值 整数 力扣 239 滑动

给定一个整数数组和一个滑动窗口大小,求在这个窗口的滑动过程中,每个时刻其包含的最大值。

示例:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值


[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

输入是一个一维整数数组,和一个表示滑动窗口大小的整数;输出是一个一维整数数组,表示每个时刻时的窗口内最大值。

可以利用双端队列进行操作:每当向右移动时,把窗口左端的值从队列左端剔除,把队列右边小于窗口右端的值全部剔除。这样双端队列的最左端永远是当前窗口内的最大值。另外,这道题也是单调栈的一种延申:该双端队列利用从左到右递减来维持大小关系。

标签:窗口,队列,双端,最大值,整数,力扣,239,滑动
From: https://www.cnblogs.com/Jojo-L/p/16608522.html

相关文章

  • 【队列】力扣218:天际线问题
    给定建筑物的起止位置和高度,返回建筑物轮廓(天际线)的拐点。输入是一个二维整数数组,表示每个建筑物的[左端,右端,高度];输出是一个二维整数数组,表示每个拐点的横纵坐标。......
  • 力扣-15-三数之和
    直达链接前两天刚做了梦开始的地方两数之和常规思路是二层遍历,对于每个数都去遍历数组找有没有刚好能凑成指定数字的进阶思路是使用hashmap,一次遍历,对于每个元素去看hah......
  • 【.Net力扣刷题】第1302题:层数最深叶子节点的和
    题目描述来源:力扣(LeetCode)链接:https://leetcode.cn/problems/deepest-leaves-sum/给你一棵二叉树的根节点root,请你返回层数最深的叶子节点的和。题目分析本题需......
  • 力扣|Q1834单线程CPU-SingleThreadedCPU
    Q1834SingleThreadedCPU简介给你一个二维数组tasks,用于表示n​​​​​​项从0到n-1编号的任务。其中tasks[i]=[enqueueTimei,processingTimei]意味着第i......
  • 410. 分割数组的最大值
     labuladong题解难度困难723收藏分享切换为英文接收动态反馈给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。设计......
  • 【搜索】力扣934:最短的桥
    在给定的二维二进制数组 A 中,存在两座岛。(岛是由四面相连的1形成的一个最大组。)现在,我们可以将 0 变为 1,以使两座岛连接起来,变成一座岛。返回必须翻转的 0的最......
  • 239.sliding-window-maxium 滑动窗口最大值
    采用双端队列deque,并且保证deque从前往后依次递减,并且出现在deque里面的相邻两数,其在原滑动窗口中,两数中间的数一定比这两个数小。为了保证这一点,在push_back()时,如果deque......
  • 洛谷 P6242 【模板】线段树 3 吉司机线段树 区间取最小值 维护历史最大值和区间和
    题目背景本题是线段树维护区间最值操作与区间历史最值的模板。题目描述给出一个长度为 nn 的数列 AA,同时定义一个辅助数组 BB,BB 开始与 AA 完全相同。接下来......
  • 力扣-刷题-324. 摆动排序 II
    题目链接来源:力扣(LeetCode)链接:https://leetcode.cn/problems/wiggle-sort-ii著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。题目描述给你一个......
  • 力扣-88-合并两个有序数组
    本来觉得很简单,然后准备提交了发现要在数组1里面合并,没有额外空间然后就有了一个大胆的想法——我直接插进去然后sortclassSolution{public: voidmerge(vector<int>......