首页 > 试题广场 >

滑动窗口的最大值

[编程题]滑动窗口的最大值

热度指数：581351 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{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]}。

窗口大于数组长度或窗口长度为0的时候，返回空。

数据范围： $1 \le n \le 10000$ ， $0 \le size \le 10000$ ，数组中每个元素的值满足 $|val| \le 10000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[2,3,4,2,6,2,5,1],3

输出

[4,4,6,6,6,5]

示例2

输入

[9,10,9,-7,-3,8,2,-6],5

输出

[10,10,9,8]

示例3

输入

[1,2,3,4],5

输出

[]

算法知识视频讲解

牛客题解官

发表于 2020-06-02 11:02:37

精华题解描述这是一篇针对初学者的题解。共用两种方法解决。从暴力算法一步步到最优算法。知识点：数组，队列难度：二星题解题目描述：给定一个数组num和一个窗口大小size，求每个窗口的最大值。方法一：暴力方法根据题目描述，我们很容易想到暴力方法。并且也很轻松的就可以写出来。如果数组的大小是n，窗口的展开全文

牛客题解官

发表于 2022-04-22 12:17:06

精华题解题目主要信息：要寻找每个滑动窗口的最大值，每次只滑一位 size等于0或者大于数组长度，都返回空值举一反三：学习完本题的思路你可以解决双向队列或者滑动窗口的题目： BM92.最长无重复子数组方法一：双向队列（推荐使用）知识点：双向队列如果说队列是一种只允许从尾部进入，从头部出来的线性展开全文

Zhuwanxing

发表于 2021-07-18 17:12:53

精华题解题目链接 https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&&tqId=11217&rp=1&ru=/ta/coding-interviews&qru=/ta/ 展开全文

NumPy

发表于 2021-07-13 18:20:05

精华题解一、题目描述 JZ64滑动窗口的最大值题目大意：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值注意审题：窗口大于数组长度的时候，返回空二、算法1（暴力）解题思路根据题目意思，枚举所有的滑动窗口，对于每个窗口，求一下最大值即可，暴力枚举所有滑动窗口的时间复杂度为比较高，一般来说都会展开全文

GhostLX

发表于 2021-06-16 21:31:38

精华题解一、题目描述题目大意：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值，窗口大于数组长度的时候，返回空。二、算法一：暴力算法思路如果num数组为空，或者num数组长度小于窗口长度，或者窗口长度非正，这些情况都没有区间最大值，则直接返回一个空的vector 当然，你可以直接写ve 展开全文

认认真真coding

发表于 2021-07-19 16:21:23

精华题解题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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] 展开全文

BillyHao

发表于 2020-02-10 12:54:25

import java.util.*; //思路：用一个大顶堆，保存当前滑动窗口中的数据。滑动窗口每次移动一格，就将前面一个数出堆，后面一个数入堆。 public class Solution { public PriorityQueue<Integer> maxQueue = 展开全文

LY789ZXY

发表于 2020-04-01 21:58:56

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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, 展开全文

designeer

发表于 2021-11-09 11:13:58

算法思想一：暴力法（窗口数组）解题思路：主要通过遍历所有的滑动窗口，找到每一个窗口的最大值，窗口的数量为 len(num) - size + 1 1、特殊情况：窗口大小为0或者窗口大于数组的长度，直接返回空列表 2、初始化返回列表res，遍历所有滑动窗口 3、找到窗展开全文

Java小白zzm

发表于 2020-03-02 23:14:57

思路：使用一个单调递减栈保存数组下标，用单调递减栈的原因是为了使栈的最左是当前窗口的最大值，如果用递增栈无法保证栈的右边是当前栈的最大值。循环遍历如果数据过期就弹出保证当前栈的最左边是该窗口最大值的坐标。 import java.util.*; public class Solution { 展开全文

岩之痕

发表于 2019-08-11 09:18:58

题目数组num的长度为N，求其所有长度为W的连续区间的最大值。一、平衡树直接用map来对每个出现的值计数，map可以直接加入，删除，求最大。时间复杂度O(NlogW)空间复杂度O(N) 二、Sparse Table 利用Sparse_Table算法思想，将区间[A, A + W) 分解成[A 展开全文

cloud_offer++

发表于 2020-03-21 16:42:38

题目给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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 展开全文

ccจุ๊บ

发表于 2020-02-19 23:42:47

python 切片它不香吗？ # -*- coding:utf-8 -*- class Solution: def maxInWindows(self, num, size): # write code here if not num or not size: 展开全文

勇敢牛牛不怕困难～

发表于 2020-12-17 11:12:12

这个方法最坏的时间复杂度为o(size*num.length)，最优为O(n)。核心思想是记录每一次窗口的最大值及所属下标，当窗口滑动时只需判断新加入的值是否比最大值大，之前的最大值有没有被滑出去。 import java.util.ArrayList; public class Solution 展开全文

-Nil-

发表于 2022-05-08 15:34:53

/** * * @param num int整型一维数组 * @param size int整型 * @return int整型一维数组 */ //使用双端队列 //遍历次数超过k时，就把上一个区间里的最大值删掉 //i从k-1开始，就可以把队列里的最大值加入结果数组 func max 展开全文

重铸广师荣光

发表于 2022-05-25 18:13:34

基本思路：双向队列，控制着数组坐标的进出。 1.在一个窗口中，把坐标放到双向队列的末尾，当但要进去的数值大于末尾的值，则把末尾的坐标值弹出，再把改值放进去。 2.当当前窗口大于当前坐标一个窗口距离时，弹出第一个节点 3.当i大于当前窗口的值时，就可以把双向队列第一个数值放在集合里面。展开全文

问题信息

队列堆双指针

难度：

1328条回答 3112收藏 121035浏览

通过挑战的用户

查看代码

牛客3340351号

2023-03-13 12:47:57
emo的大熊猫...

2023-02-19 21:42:27
Elastic...

2023-02-13 22:42:41
痛苦的C语言人

2023-02-03 09:04:13
AAA牛牛

2022-12-18 01:44:44

滑动窗口的最大值

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题