首页 > 试题广场 >

滑动窗口的最大值

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

热度指数：581568 时间限制：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

输出

[]

算法知识视频讲解

推荐

lizo

import java.util.*;
/**
用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较，把所有比他小的值丢掉
*/
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
       	if(size == 0) return res;
		int begin;	
		ArrayDeque<Integer> q = new ArrayDeque<>();
		for(int i = 0; i < num.length; i++){
			begin = i - size + 1;
			if(q.isEmpty())
				q.add(i);
			else if(begin > q.peekFirst())
                q.pollFirst();
		
			while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
			q.add(i);	
			if(begin >= 0)
				res.add(num[q.peekFirst()]);
		}
		return res;
    }
}

编辑于 2015-09-02 14:11:26 回复(51)

Python

一直菜菜鸟

class Solution:
    def maxInWindows(self, num, size):
	first = 0
	last = size - 1
	numSnap = num[first:last+1]
	maxValue = max(numSnap)
	maxIndex = num.index(maxValue)
	res = [maxValue]
	first += 1
	last += 1
	while last < len(num):
		if first == maxIndex + 1:
			numSnap = num[first:last+1]
			maxValue = max(numSnap)
			maxIndex = numSnap.index(maxValue) + first
		if num[last] > maxValue:
			maxValue = num[last]
			maxIndex = last
		res.append(maxValue)
		first += 1
		last += 1
	return res

发表于 2022-08-26 11:04:29 回复(0)

Python

又要找工作了

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size == 0&nbs***bsp;num == []&nbs***bsp;len(num) < size:
            return []
        results = []
        for i in range(len(num)- size + 1):
            nums = num[i:i+size]
            results.append(max(nums))
        return results

编辑于 2021-09-10 14:40:06 回复(0)

Python

牛客987449563号

def maxInWindows(self, num, size):
# write code here
if size == 1:
return num
res = []
len_num = len(num)
for i in range(1, size):
for j in range(len_num - i):
num[j] = max(num[j], num[j+1])
if i == size - 1:
res.append(num[j])

return res

递归思想，由小问题到大问题：size=3的计算为size=2的结果的两个临近位置的最大值；size=2的计算为size=1的两个临近位置的最大值。O(N*M)

发表于 2021-07-25 10:15:44 回复(0)

Python

不愿吃饼的三文鱼很调皮

这也能过。。

class Solution:
    def maxInWindows(self, num, size):
        if size > len(num): return None
        if size == 0: return []
        cur = size - 1
        res = []
        while cur < len(num):
            res.append(max(num[cur-size+1:cur+1]))
            cur += 1
        return res

发表于 2021-06-29 09:41:56 回复(0)

Python

lilijijiguo

使用三指针实现滑动窗口的最大值，无堆栈队列，python 16ms

class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size==0&nbs***bsp;size>len(num):
            return []
        rtn = []
        max_idx = 0
        for idx in range(size):
            if num[idx]>num[max_idx]:
                max_idx=idx
        rtn.append(num[max_idx])
        idx = size
        cur_idx = idx
        while idx<len(num):
            if idx-max_idx>=size:
                max_idx += 1
                idx = max_idx 
            else:
                if num[idx]>num[max_idx]:
                    max_idx = idx
                if idx==cur_idx:
                    rtn.append(num[max_idx])
                    cur_idx += 1
                idx += 1
            
        return rtn

编辑于 2021-06-04 21:22:50 回复(0)

Python

kk-li

class Solution:
def maxInWindows(self, num, size):
# write code here
res = []
if len(num)>=size and size:
for i in range(len(num)-size+1):
res.append(max(num[i:i+size]))
return res

发表于 2021-05-08 20:50:39 回复(0)

Python

牛客541273514号

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size>len(num)&nbs***bsp;size==0:
            return []
        res=[]
        n=len(num)
        for i in range(n-size+1):
            res.append(max(num[i:i+size]))
        return res

发表于 2021-05-03 18:21:26 回复(0)

Python

Hiroi

Python 循环。

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size>len(num):
            return []
        if size==0:
            return []
        output = []
        for i in range(len(num)-size+1):
            #     1,2,3,4,5
            # 0:3 1,2,3
            # 1:4 2,3,4
            # 2:5 3,4,5
            # len(num)=5,size=3
            temp = max(num[i:i+size])
            output.append(temp)
        return output

发表于 2021-04-18 21:25:30 回复(0)

Python

老和山小学生

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size < 1:
            return []
        queue = []
        res = []
        i = 0
        while i < len(num):
            while queue and queue[0] <= i-size:
                queue.pop(0)
            while queue and num[i] > num[queue[-1]]:
                queue.pop()
            queue.append(i)
            if i >= size-1:
                res.append(num[queue[0]])
            i += 1
        return res

发表于 2020-10-16 17:09:22 回复(0)

Python

牛客157263743号

class Solution:
    def maxInWindows(self, num, size):
        # write code here
        maxi=[]
        if not (len(num)<size&nbs***bsp;size<=0):
            for i in range(len(num)):
                if (i+size)<=len(num):
                    m=max(num[i:i+size])
                    maxi.append(m)
        return maxi

发表于 2020-08-13 21:04:13 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        length = len(num)
        if size > length&nbs***bsp;size <= 0:
            return []
        sum = []
        for i in range(0,length-size+1):
            sum.append(max(num[i:i+size]))
        return sum

发表于 2020-07-30 11:07:59 回复(0)

Python

VanPersie

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if (len(num)==0 or size>len(num) or size<=0):
            return []
        a = []
        for i in range(0, len(num)-size + 1):
            a.append(max(num[i:(size+i)]))
        return a

编辑于 2020-06-15 11:03:24 回复(0)

Python

橘子汽水超人2号

Python Solution

class Solution:
    def maxInWindows(self, num, size):
        res = []
        if size>len(num) or size<=0:return []
        for i in range(len(num)-size+1):
            res.append(max(num[i:i+size]))
        return res

编辑于 2020-06-05 18:23:59 回复(0)

Python

Chloe_y

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size == 0:
            return []
        result = []
        for i in range(len(num)-size+1):
            ls = []
            for j in range(size):
                ls.append(num[i+j])
            res = max(ls)
            result.append(res)
        return result

发表于 2020-05-31 19:59:33 回复(0)

Python

Kuriyamaaa

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        if num==[]:
            return []
        if size<=0:
            return []
        if size==1:
            return num
        if size==len(num):
            return[ max(num)]
        if size>len(num):
            return []
        maxx=max(num[0:size])
        re=[maxx]
        index=num.index(maxx)
        for i in range(1,len(num)-size+1,1):
            if index in range(i,i+size):
                if maxx<=num[i:i+size][-1]:
                    maxx=num[i:i+size][-1]
                    index=i+size-1
                    re.append(maxx)
                else:
                    re.append(maxx)
            else:
                maxx=max(num[i:i+size])
                index=num[i:i+size].index(maxx)+i
                re.append(maxx)
        return re

发表于 2020-05-28 15:28:10 回复(0)

Python

牛客341441072号

class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size==0:
            return []
        left = 0
        right = size
        res = []
        while right<=len(num):
            res.append(max(num[left:right]))
            left+=1
            right+=1
        return res

发表于 2020-05-08 14:30:46 回复(0)

Python

朝夕_

class Solution:
    def maxInWindows(self, num, size):
        a = []
        if num:
            if 0 < size <= len(num):
                for i in range(len(num)-size+1):
                    a.append(max(num[i:i+size]))
        return a

发表于 2020-03-01 15:32:10 回复(0)

Python

ghostinthecode

看来一圈，感觉大佬们的解释对新手不是太友好，来一个详细版本的。

如何把复杂度降低到线性的呢。由于size的值是给定的，也就是程序运行开始，到结束size不变。那么我们可以来维护这样一个队列，左边出右边进。并且当进来的元素的时候，我们需要让最左边的元素始终为最大的那个。举个栗子?nums=[1,3, -1,-3,5,3]，一开始为【1】添加，【1】，先进行维护，然后添加了3，【3】，添加【3，-1】，维护，不发生变化，添加【3，-1，-3】，维护不发生变化，添加【-1，-3】，维护后添加了5，得【5】。通过代码可以，维护一个window的时候，可以大致认为为平均下来为O（1），那么整体就是一个线性复杂度。希望对你们理解这题有帮助吧

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if not num&nbs***bsp;not size: return []
        window, result = [], []
        for i, x in enumerate(num):
            #为了使得window一直为size,注意window里面的是Index，给人一种移动的感觉
            if i >= size and window[0] <=i-size:
                window.pop(0)
            #下面是维护的代码，当队列里的数字，小于当前值的是就pop掉
            while window and num[window[-1]] <= x:
                window.pop()
            window.append(i)
            if i>= size-1:
                result.append(num[window[0]])
        return result

发表于 2020-02-11 22:10:12 回复(0)

Python

黄沙遮天

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.list1=[]
    def maxInWindows(self, num, size):
        # write code here
        if num ==None:
            return None
        if size<=0&nbs***bsp;size>len(num):
            return []
        i=0
        while(i+size)<=len(num):
            self.list1.append(max(num[i:i+size]))
            i+=1
        return self.list1

此题的关键是确定几个边界条件，首先是size小于等于0或者size大于num数组的长度时都返回【】

发表于 2020-02-06 21:58:03 回复(0)

提交观点

问题信息

队列堆双指针

难度：

72条回答 3115收藏 121066浏览

通过挑战的用户

查看代码

牛客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

滑动窗口的最大值

输入

输出

输入

输出

输入

输出

Python Solution

问题信息

热门推荐

通过挑战的用户

相关试题