JavaScript日拱算法题解滑动窗口的最大值示例
题目:
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
示例: 输入: 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
题目来源:剑指 Offer 59 - I. 滑动窗口的最大值
题解:
第一反应
有时候搞不太懂力扣对于难度等级的判定,此题为“困难”?
用长度为 k 的数组去遍历 nums 就可以了,每次拿到它的最大值,然后push进结果数组中,再返回不就行了?
分步解析:
1.找到窗口从头滑到尾需要滑动的次数为: nums.length - k + 1;
2.初始化队列;
3.每次滑动的时候,找到当前窗口的最大值保存到 res 数组,然后执行删除队列头元素、在队列尾添加下一元素的操作;
JavaScript 实现
var maxSlidingWindow = function(nums, k) { if (nums.length == 0 || k > nums.length) return [] var index = k var len = nums.length - k + 1 var stack = [], res = [] for (var j = 0; j < k; j++) { stack.push(nums[j]) } for (i = 0; i < len; i++) { if (i !== 0) { stack.shift() stack.push(nums[index]) index++ } res.push(Math.max.apply(null, stack)) } return res };
提交看看,结果报错“超出时间限制” QAQ
噢噢,再回看算法,for 循环里面要对数组一整个 Math.max,时间复杂度肯定爆表了,O(n*n),不超时才怪。
第二反应
正解:转换思路 采用单调数列
依次将数组的下标push到窗口中,超出窗口的shift掉,窗口是个单调递减队列,队头元素就是当前窗口的最大值;
步骤拆解:
1、每当读入的数大于队尾,则循环删除队尾小于读入元素的数字,保证队列的递减单调性
2、如果单调的队首(极大值),等于窗口左边界的上一位,则说明极大值已经超出窗口,移除单调递减队列的队首
3、每次窗口滑动的最大值为,单调递减队列的队首
4、循环以上步骤,直到窗口的右边界到队尾
JS 实现
var maxSlidingWindow = function(nums, k) { const res = []; //保存滑动窗口的最大值 const q = []; //滑动窗口队列 for (let i = 0; i < nums.length; i++) { //1.在队尾添加元素num[i] var last = q.length - 1; //队列的最后一个元素的索引 while (last >= 0 && nums[i] > q[last]) { //2.循环求解序列中的最大值 //2.求队列中的最大值:如果新入队列的元素,比队尾元素大,队尾被更新成新入队列的元素,保证队头为队列中的最大元素 q.pop(); //队尾移除, last = q.length - 1; //队列更新长度 } q.push(nums[i]); //入队列 // 当窗口i + 1 - k >= 0时,窗口满了有三个数了 const j = i + 1 - k; //窗口向右滑动过程中最后一个元素的索引。 if (j >= 0) { res.push(q[0]); //保存每一次k个窗口的最大值 if (nums[j] === q[0]) { //3.向有滑动过程中,如果序列中的最大元素即退出窗口,则移除队列头部元素 q.shift(); // } } } return res; };
小结:
除了以上两种解法,还有其它思路,不得不说这题还是很有学问的。在处理滑动窗口问题中,经常会遇到要构造一个单调队列,得着重记笔记记笔记。(ಥ﹏ಥ)
以上就是JavaScript日拱算法题解滑动窗口的最大值示例的详细内容,更多关于JavaScript 滑动窗口最大值的资料请关注猪先飞其它相关文章!
原文出处:https://juejin.cn/post/7137665757575381023
相关文章
使用PHP+JavaScript将HTML页面转换为图片的实例分享
这篇文章主要介绍了使用PHP+JavaScript将HTML元素转换为图片的实例分享,文后结果的截图只能体现出替换的字体,也不能说将静态页面转为图片可以加快加载,只是这种做法比较interesting XD需要的朋友可以参考下...2016-04-19- 在昨天的《Javascript权威指南》学习笔记之十:ECMAScript 5 增强的对象模型一文中,对于一段代码的调试出现了一个奇怪现象,现将源代码贴在下面: 复制代码 代码如下: <script type="text/javascript"> function Person(){}...2014-05-31
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 复制代码 代码如下: //element:需要添加新样式的元素,value:新的样式 function addClass(element, value ){ if (!element.className){ element.className = value; }else { newClassName = element.className; newClas...2014-05-31
- 在javascritp中,不一定只有对象方法的上下文中才有this, 全局函数调用和其他的几种不同的上下文中也有this指代。 它可以是全局对象、当前对象或者任意对象,这完全取决于函数的调用方式。JavaScript 中函数的调用有以下...2015-03-15
- 有一道js面试题,题目是这样的:下列代码的执行结果是什么,为什么? 复制代码 代码如下: var i, j, k; for (i=0, j=0; i<10, j<6; i++, j++) { k = i+j; } document.write(k); 答案是显示10,这道题主要考察JavaScript的逗...2015-03-15
- 事件触发器从字面意思上可以很好的理解,就是用来触发事件的,但是有些没有用过的朋友可能就会迷惑了,事件不是通常都由用户在页面上的实际操作来触发的吗?这个观点不完全正确,因为有些事件必须由程序来实现,如自定义事件,jQue...2014-06-07
- 首先,我想到的是另建一个结果数组,用来存储原始数组中不重复的数据。遍历原始数组依次跟结果数组中的元素进行比较,检测是否重复。于是乎,我写出了如下代码A: Array.prototype.clearRepetitionA = function(){ var resul...2015-11-08
- 1、ActiveX向Javascript传参 复制代码 代码如下: <script language="javascript" for="objectname" event="fun1(arg)"> fun2(arg); </script> objectname为ActiveX控件名,通过<object>标签里的id属性设定,如下; 复制...2014-06-07
- 这篇文章主要介绍了Javascript类型转换的规则实例解析,涉及到javascript类型转换相关知识,对本文感兴趣的朋友一起学习吧...2016-02-27
- Window有navigator对象让我们得知浏览器的全部信息.我们可以利用一系列的API函数得知浏览器的信息.JavaScript代码如下:function message(){ txt = "<p>浏览器代码名: " + navigator.appCodeName + "</p>";txt+= "<p>...2015-11-24
- 通过 HTML DOM,可访问 JavaScript HTML 文档的所有元素。 HTML DOM (文档对象模型) 当网页被加载时,浏览器会创建页面的文档对象模型(Document Object Model)。 HTML DOM 模型被构造为对象的树: 通过可编程的对象模型,Java...2015-10-23
- 虽然ES6都还没真正发布,但已经有用ES6重写的程序了,各种关于ES789的提议已经开始了,这你敢信。潮流不是我等大众所能追赶的。潮流虽然太快,但我们不停下学习的步伐,就不会被潮流丢下的,下面来领略下ES6中新特性,一堵新生代JS...2015-11-24
- 神马是“解释器模式”?先翻开《GOF》看看Definition:给定一个语言,定义它的文法的一种表示,并定义一个解释器,这个解释器使用该表示来解释语言中的句子。在开篇之前还是要科普几个概念: 抽象语法树: 解释器模式并未解释如...2014-06-07
- ---恢复内容开始---1.location.href.....(1)self.loction.href="http://www.cnblogs.com/url" window.location.href="http://www.cnblogs.com/url" 以上两个用法相同均为在当前页面打开URL页面 (2)this.locati...2015-10-30
- tab切换在网页中很常见,故最近总结了4种实现方法。 首先,写出tab的框架,加上最简单的样式,代码如下: <!DOCTYPE html> <html> <head><meta http-equiv="Content-Type" content="text/html; charset=utf-8" /><style> *{ pa...2015-11-08
基于JavaScript如何实现私有成员的语法特征及私有成员的实现方式
前言在面向对象的编程范式中,封装都是必不可少的一个概念,而在诸如 Java,C++等传统的面向对象的语言中, 私有成员是实现封装的一个重要途径。但在 JavaScript 中,确没有在语法特性上对私有成员提供支持, 这也使得开发人员使...2015-10-30- 这篇文章主要介绍了JavaScript预解析,对象的的相关资料,小编觉得这篇文章写的还不错,需要的朋友可以参考下,希望能够给你带来帮助...2021-11-10
- 生生把写过的java版改成javascript版,第一次写,很不专业,见谅。唉,我是有多闲。复制代码 代码如下: var Sudoku = { init: function (str) { this.blank = []; this.fixed = []; this.cell =...2015-03-15
javascript中slice(),splice(),split(),substring(),substr()使用方法
1.slice();Array和String对象都有在Array中 slice(i,[j])i为开始截取的索引值,负数代表从末尾算起的索引值,-1为倒数第一个元素 j为结束的索引值,缺省时则获取从i到末尾的所有元素参数返回: 返回索引值从i到j的数组,原数组...2015-03-15