239. Sliding Window Maximum滑动窗口的最大值

2024-01-04 19:39

本文主要是介绍239. Sliding Window Maximum滑动窗口的最大值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

解答

暴力法

  遍历每一个滑动窗口,找到其中的最大值。如果滑动窗口的大小为k,需要O(k)时间才能找到窗口中的最大值。对于长度为n的输入数组,这个算法的时间复杂度是O(nk)。

使用包含max的栈模仿队列

  实际上,一个滑动窗口可以看作一个队列。当窗口滑动时,处于窗口的第一个数字被删除,同时在窗口的末尾添加一个新的数字。这符合队列先进先出的特性。
在155. Min Stack&包含min函数的栈中,我们实现了一个可以用O(1)时间得到最小值的栈。同样,我们可以实现用O(1)时间得到最大值的栈。同时我们可以用两个栈实现一个队列。
  综合这两个算法,我们发现,如果用两个包含max操作的栈来实现队列,就可以在O(1)时间内得到队列的最大值,也就可以将时间复杂度降低到O(n)。

使用deque

  实际上,我们并不需要将滑动窗口的每个值都存入队列中,而只把有可能成为滑动窗口最大值的数值存入到一个两端开口的队列(deque)中
  下面以{2,3,4,2,6,2,5,1},窗口尺寸为3来分析。
  数组的第一个数字是2,把它加入deque。第二个数字是3,由于它比前一个数字2大,因此2不可能成为滑动窗口中的最大值。所以把2从deque中删掉,将3加入队列。此时deque中只有一个数字3。针对第三个数字4的步骤类似。最终在deque中只剩下一个数字4。此时,滑动窗口中已经有三个数字,其最大值4位于deque的头部。
  接下来处理第四个数字2。2比deque中的数字4小,但是当4滑出窗口后,2还是有可能成为滑动窗口中的最大值。因此把2存入deque的尾部。现在deque中有两个数字4和2,滑动窗口的最大值4仍然在deque的头部。
  下一个数字是6。因为它比deque中已经存在的两个数字4和2都要大,所以此时4和2已经不可能成为滑动窗口的最大值了。所以先把4和2从deque中移除,然后把6加入deque中。此时滑动窗口的最大值6在deque的头部。
  接下来是2。与位于第四位的2一样,将其加入deque的尾部。此时deque中有两个数字6和2,滑动窗口的最大值6仍然在deque的头部。
  接下来的数字是5。在deque中已有的两个数字6和2中,2小于5,所以2不可能是一个滑动窗口的最大值,所以把2从deque尾部移除,然后将5加入deque。此时deque中有两个数字6和5,滑动窗口的最大值6仍然在deque的头部。
  最后一个数字是1,与处理第4位和第6位的2一样,将其加入队尾。注意到此时位于deque头部的6此时已经不在滑动窗口中,所以要将其移除。此时滑动窗口中有两个数5和1,滑动窗口的最大值5仍然在deque的头部。
  PS:如何判断一个数字是否在滑动窗口中?
  应该在deque中存储数字在数组中的下标,而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或等于滑动窗口的尺寸时,这个数字就已经不再滑动窗口中了,可以将它从队首删去。

vector<int> maxInWindows(const vector<int>& num, unsigned int size){vector<int> maxInWindows;if(num.size()>=size && size>=1){deque<int> indexDeque;for(int i = 0;i<size;++i){while(!indexDeque.empty() && num[i] >=num[indexDeque.back()])indexDeque.pop_back();indexDeque.push_back(i);}for(int i = size;i<num.size();++i){maxInWindows.push_back(num[indexDeque.front()]);//将当前队列中不可能是滑动窗口中最大值的删掉while(!indexDeque.empty() && num[i] >=num[indexDeque.back()])indexDeque.pop_back();//将已经不在滑动窗口内的值删掉if(!indexDeque.empty()&&indexDeque.front()<=i-size)indexDeque.pop_front();indexDeque.push_back(i);}maxInWindows.push_back(num[indexDeque.front()]);}return maxInWindows;}

这篇关于239. Sliding Window Maximum滑动窗口的最大值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/570389

相关文章

Python使用Pandas对比两列数据取最大值的五种方法

《Python使用Pandas对比两列数据取最大值的五种方法》本文主要介绍使用Pandas对比两列数据取最大值的五种方法,包括使用max方法、apply方法结合lambda函数、函数、clip方法、w... 目录引言一、使用max方法二、使用apply方法结合lambda函数三、使用np.maximum函数

Window Server创建2台服务器的故障转移群集的图文教程

《WindowServer创建2台服务器的故障转移群集的图文教程》本文主要介绍了在WindowsServer系统上创建一个包含两台成员服务器的故障转移群集,文中通过图文示例介绍的非常详细,对大家的... 目录一、 准备条件二、在ServerB安装故障转移群集三、在ServerC安装故障转移群集,操作与Ser

Window Server2016加入AD域的方法步骤

《WindowServer2016加入AD域的方法步骤》:本文主要介绍WindowServer2016加入AD域的方法步骤,包括配置DNS、检测ping通、更改计算机域、输入账号密码、重启服务... 目录一、 准备条件二、配置ServerB加入ServerA的AD域(test.ly)三、查看加入AD域后的变

Window Server2016 AD域的创建的方法步骤

《WindowServer2016AD域的创建的方法步骤》本文主要介绍了WindowServer2016AD域的创建的方法步骤,文中通过图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、准备条件二、在ServerA服务器中常见AD域管理器:三、创建AD域,域地址为“test.ly”

bat脚本启动git bash窗口,并执行命令方式

《bat脚本启动gitbash窗口,并执行命令方式》本文介绍了如何在Windows服务器上使用cmd启动jar包时出现乱码的问题,并提供了解决方法——使用GitBash窗口启动并设置编码,通过编写s... 目录一、简介二、使用说明2.1 start.BAT脚本2.2 参数说明2.3 效果总结一、简介某些情

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法,它将时间划分为若干个固定大小的窗口,每个窗口内记录了该时间

使用JS/Jquery获得父窗口的几个方法(笔记)

<pre name="code" class="javascript">取父窗口的元素方法:$(selector, window.parent.document);那么你取父窗口的父窗口的元素就可以用:$(selector, window.parent.parent.document);如题: $(selector, window.top.document);//获得顶级窗口里面的元素 $(

js window.addEventListener 是什么?

window.addEventListener 是 JavaScript 中的一个方法,用于向指定对象(在这个情况下是 window 对象,代表浏览器窗口)添加事件监听器,以便在该对象上发生特定事件时执行相应的函数(称为事件处理函数或事件监听器)。 这个方法接受三个参数: 事件类型(type):一个字符串,表示要监听的事件类型。例如,"click" 表示鼠标点击事件,"load" 表示页面加

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

Qt中window frame的影响

window frame 在创建图形化界面的时候,会创建窗口主体,上面会多出一条,周围多次一圈细边,这就叫window frame窗口框架,这是操作系统自带的。 这个对geometry的一些属性有一定影响,主要体现在Qt坐标系体系: 窗口当中包含一个按钮,这个按钮的坐标系是以父元素为参考,那么这个参考是widget本体作为参考,还是window frame作为参考,这两种参考体系都存在