首页 > 试题广场 > 滑动窗口的最大值
[编程题]滑动窗口的最大值
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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]}。
推荐
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 回复(37)
//引用马客(Mark)的解题思路,马客没加注释,我用自己的理解加下注释,希望对你们有用,
//如有错误,见谅,我会及时修改。
//deque s中存储的是num的下标
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        deque<int> s;
        for(unsigned int i=0;i<num.size();++i){
            while(s.size() && num[s.back()]<=num[i])//从后面依次弹出队列中比当前num值小的元素,同时也能保证队列首元素为当前窗口最大值下标
                s.pop_back();
            while(s.size() && i-s.front()+1>size)//当当前窗口移出队首元素所在的位置,即队首元素坐标对应的num不在窗口中,需要弹出
                s.pop_front();
            s.push_back(i);//把每次滑动的num下标加入队列
            if(size&&i+1>=size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
                res.push_back(num[s.front()]);
        }
        return res;
    }
};

编辑于 2016-06-27 16:21:02 回复(24)
/**
 * 题目:滑动窗口的最大值
 * 思路:滑动窗口应当是队列,但为了得到滑动窗口的最大值,队列序可以从两端删除元素,因此使用双端队列。
 *     原则:
 *     对新来的元素k,将其与双端队列中的元素相比较
 *     1)前面比k小的,直接移出队列(因为不再可能成为后面滑动窗口的最大值了!),
 *     2)前面比k大的X,比较两者下标,判断X是否已不在窗口之内,不在了,直接移出队列
 *     队列的第一个元素是滑动窗口中的最大值
 */
public class P65_滑动窗口的最大值 {
	
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
    	ArrayList<Integer> ret = new ArrayList<>();
    	if (num == null) {
    		return ret;
    	}
    	if (num.length < size || size < 1) {
    		return ret;
    	}
    	
    	LinkedList<Integer> indexDeque = new LinkedList<>();
    	for (int i = 0; i < size - 1; i++) {
    		while (!indexDeque.isEmpty() && num[i] > num[indexDeque.getLast()]) {
    			indexDeque.removeLast();
    		}
    		indexDeque.addLast(i);
    	}
    	
    	for (int i = size - 1; i < num.length; i++) {
    		while (!indexDeque.isEmpty() && num[i] > num[indexDeque.getLast()]) {
    			indexDeque.removeLast();
    		}
    		indexDeque.addLast(i);
    		if (i - indexDeque.getFirst() + 1 > size) {
    			indexDeque.removeFirst();
    		}
    		ret.add(num[indexDeque.getFirst()]);
    	}
        return ret;
    }
}

编辑于 2016-04-10 23:18:06 回复(6)
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if (num == null || num.length == 0 || size <= 0 || num.length < size) {
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> result = new ArrayList<>();
        //双端队列,用来记录每个窗口的最大值下标
        LinkedList<Integer> qmax = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < num.length; i++) {
            while (!qmax.isEmpty() && num[qmax.peekLast()] < num[i]) {
                qmax.pollLast();
            }
            qmax.addLast(i);
            //判断队首元素是否过期
            if (qmax.peekFirst() == i - size) {
                qmax.pollFirst();
            }
            //向result列表中加入元素
            if (i >= size - 1) {
                result.add(num[qmax.peekFirst()]);
            }
        }
        return result;
    }
}

发表于 2018-03-10 21:55:47 回复(5)
//单调队列,O(n)
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& a, unsigned int k){
        vector<int> res;
        deque<int> s;
        for(unsigned int i = 0; i < a.size(); ++i){
            while(s.size() && a[s.back()] <= a[i]) s.pop_back();
            while(s.size() && i - s.front() + 1 > k) s.pop_front();
            s.push_back(i);
            if(k && i + 1 >= k) res.push_back(a[s.front()]);
        }
        return res;
    }
};

编辑于 2015-09-17 14:02:16 回复(6)
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> list  = new ArrayList<Integer> ();
        if(size>num.length||size==0)
            return list;
        for(int i = 0;i<=num.length-size;i++){
            int max = num[i];
            for(int j = i+1;j<i+size;j++){
                if(num[j]>max){
                    max = num[j];
                }
            }
            list.add(max);
        }
        return list;
    }
}

发表于 2016-04-18 13:45:11 回复(10)
Python solution
1. 利用python性质每次求固定size的最大值,时间复杂度O(n*size)
res, i = [], 0
while size > 0 and i + size - 1 < len(num):
    res.append(max(num[i:i + size]))
    i += 1
return res

2. 双向队列,queue存入num的位置,时间复杂度O(n)
queue,res,i = [],[],0
while size>0 and i<len(num):
    if len(queue)>0 and i-size+1 > queue[0]: #若最大值queue[0]位置过期 则弹出  
        queue.pop(0)
    while len(queue)>0 and num[queue[-1]]<num[i]: #每次弹出所有比num[i]的数字
        queue.pop()
    queue.append(i)
    if i>=size-1:
        res.append(num[queue[0]])
    i += 1
return res
发表于 2018-10-24 22:07:14 回复(2)
class Solution {
public:
    //时间复杂度o(n),空间复杂度为o(n)
    /*思路就是采用双端队列,队列中的头节点保存的数据比后面的要大。
      比如当前假如的数据比队尾的数字大,说明当前这个数字最起码在从现在起到后面的过程中可能是最大值
      ,而之前队尾的数字不可能最大了,所以要删除队尾元素。
      此外,还要判断队头的元素是否超过size长度,由于存储的是下标,所以可以计算得到;
      特别说明,我们在双端队列中保存的数字是传入的向量的下标;
    */
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> vec;
        if(num.size()<=0 || num.size()<size ||size<=0) return vec;//处理特殊情况
        deque<int> dq;
        //处理前size个数据,因为这个时候不需要输出最大值;
        for(unsigned int i=0;i<size;i++)
        {
 //假如当前的元素比队列队尾的元素大,说明之前加入的这些元素不可能是最大值了。因为当前的这个数字比之前加入队列的更晚
            while(!dq.empty()&&num[i]>=num[dq.back()])
                dq.pop_back();//弹出比当前小的元素下标
            dq.push_back(i);//队尾压入当前下标
        }
        //处理size往后的元素,这时候需要输出滑动窗口的最大值
        for(unsigned int i=size;i<num.size();i++)
        {
            vec.push_back(num[dq.front()]);
            while(!dq.empty()&&num[i]>=num[dq.back()])
                dq.pop_back();
            if(!dq.empty() && dq.front()<=(int)(i-size))//判断队头的下标是否超出size大小,如果超过,要删除队头元素
                dq.pop_front();//删除队头元素
            dq.push_back(i);//将当前下标压入队尾,因为可能在未来是最大值
        }
        vec.push_back(num[dq.front()]);//最后还要压入一次
        return vec;
    }
};
发表于 2016-07-29 14:41:00 回复(5)
class Solution {
    public:
    
    //最大堆实现,复杂度O(nlogn)
    typedef pair<int,int> Pair;
    vector<int> maxInWindows(const vector<int> &num, unsigned int size) {
        vector<int> result;
        priority_queue<Pair> Q;
        if (num.size() < size || size < 1)
            return result;
        for (int i = 0; i < size-1; i++) 
            Q.push(Pair(num[i],i));
        for (int i = size-1; i < num.size(); i++) {
            Q.push(Pair(num[i],i));
            Pair p = Q.top();
            while(p.second < i-(size-1)) {
                Q.pop();
                p = Q.top();
            }
            result.push_back(p.first);
        }
//        result.push_back(Q.top().first);
        return result;
    }
    
    // 双向队列实现,复杂度O(n)
    
    vector<int> maxInWindows(const vector<int> &num, unsigned int size) {
        vector<int> result;
        deque<int> Q;
//        int n = num.size();
        if(num.size()<size || size<=0)
            return result;
        for (int i = 0; i < size; i++) {
            while (!Q.empty() && num[i] > num[Q.back()]) Q.pop_back();
            Q.push_back(i);
        }
        for (int i = size; i < num.size(); i++) {
            result.push_back(num[Q.front()]);
            while (!Q.empty() && num[i] >= num[Q.back()]) Q.pop_back();
            while (!Q.empty() && Q.front() <= i - size) Q.pop_front();
            Q.push_back(i);
        }
        result.push_back(num[Q.front()]);
        return result;
    }
    
};
编辑于 2015-05-06 23:13:38 回复(2)
我看见都用了队列,就想了一个不用队列的方法,虽然有点麻烦。。。

首先,用一个值index记录窗口最大值的位置,以及一个记录窗口最大值的max。
然后就可以用i遍历数组了,用index和i比较,小于就说明窗口最左边已经过了之前的那个最大值,于是从i向右size个单位找到最大值,并记录,不小于就说明最大值还在窗口内,由于窗口每次滑动都会向右移动一个元素,使用这个元素和max比较再记录。最后添加到ArrayList中。
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> list = new ArrayList<>();
        if (num == null) {
            return list;
        }
        if (num.length < size || size < 1) {
            return list;
        }
        
        int max = 0;//记录每个窗口的最大值
        int index = -1;//这个是记录这个窗口的最大值的位置
        for(int i = 0; i <= num.length - size; i++){
            if(index < i){//当最大位置的索引小于i的时候,就说明窗口过了这个元素
                max = num[i];
                for(int j = i; j < i + size; j++){//那么就从这个元素开始向后查找这个窗口的最大值
                    if(max <= num[j]){
                        index = j;
                        max = num[j];
                    }
                }
            } else{//没过的话,就判断这个窗口的最后一个元素是否比max大。
                if(max <= num[i + size - 1]){
                    index = i + size - 1;
                    max = num[i + size - 1];
                }
                
            }
            list.add(max);
        }
        return list;
    }
}

发表于 2018-05-10 10:56:54 回复(5)
被无符号整形坑了。。。
unsigned int v=1;
unsigned int b=5;
cout<<v-b<<endl; //输出4294967292,因为没有负数

 i-q_max.front()+1>size(判断是否要把队列第一个给pop出去,当它已经在窗口外时)
所以这个要这么写
之前写成
q_max.front()<i-size+1   
逻辑上是一样的,但是需要负数存在,开始还没想明白
发表于 2017-05-05 20:12:13 回复(3)
滑动窗口。
1)判断是否合法输入。
2)合法,则找出0~size-1 中最大值,其坐标为index。
3)滑动,判断index是否过期,过期则找到窗口中的最大值的index。添加到list当中。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> list=new ArrayList<Integer> ();
        if(num==null||num.length<size||size<=0) return list;
        //int max=num[0];
        int index=0;
        index=findMax(num,size,0);
        list.add(num[index]);
        for(int i=size;i<num.length;i++){
           if(index<=i-size){index=findMax(num,size,index+1);}//判断是否过期,过期则找到最新的最大值
            if(num[index]<num[i])  index=i;
            list.add(num[index]);
            
        }
        
      return list;  
    }
    public int findMax(int [] num,int size,int begin){
        
        //int max=num[begin];
        int index=begin;
        for(int i= begin+1;i< begin+size;i++){
            if(num[index]<num[i]) 
            {
               // max=num[i];
                index=i;
            }
        }
        return index;
    }
}

发表于 2016-08-30 21:55:40 回复(3)

剑指Offer-滑动窗口的最大值

package StackAndQueue;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
/**
 * 滑动窗口的最大值
 * 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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]}。
 */
public class Solution52 {
    public static void main(String[] args) {
        Solution52 solution52 = new Solution52();
        int[] num = {2, 3, 4, 2, 6, 2, 5, 1};
        int size = 3;
        ArrayList list = solution52.maxInWindows(num, size);
        System.out.println(list);
    }
    /**
     * 最大堆方法
     * 构建一个窗口size大小的最大堆,每次从堆中取出窗口的最大值,随着窗口往右滑动,需要将堆中不属于窗口的堆顶元素删除。
     *
     * [@param num
     * @param size
     * @return](/profile/547241) */
    public ArrayList maxInWindows_2(int[] num, int size) {
        ArrayList res = new ArrayList();
        if (size > num.length || size < 1) return res;
        // 构建最大堆,即堆顶元素是堆的最大值。
        PriorityQueue heap = new PriorityQueue((o1, o2) -> o2 - o1);
        for (int i = 0; i < size; i++) heap.add(num[i]);
        res.add(heap.peek());
        for (int i = 1; i + size - 1 < num.length; i++) {
            heap.remove(num[i - 1]);
            heap.add(num[i + size - 1]);
            res.add(heap.peek());
        }
        return res;
    }
    /**
     * 双队列方法
     * 滑动窗口的最大值总是保存在队列首部,队列里面的数据总是从大到小排列。
     *
     * [@param num
     * @param size
     * @return](/profile/547241) */
    public ArrayList maxInWindows(int[] num, int size) {
        ArrayList res = new ArrayList();
        if (num == null || num.length == 0 || size == 0 || size > num.length) {
            return res;
        }
        Deque deque = new LinkedList();
        for (int i = 0; i < num.length; i++) {
            if (!deque.isEmpty()) {
                // 如果队列头元素不在滑动窗口中了,就删除头元素
                if (i >= deque.peek() + size) {
                    deque.pop();
                }
                // 如果当前数字大于队列尾,则删除队列尾,直到当前数字小于等于队列尾,或者队列空
                while (!deque.isEmpty() && num[i] >= num[deque.getLast()]) {
                    deque.removeLast();
                }
            }
            deque.offer(i); // 入队列
            // 滑动窗口经过一个滑动窗口的大小,就获取当前的最大值,也就是队列的头元素
            if (i + 1 >= size) {
                res.add(num[deque.peek()]);
            }
        }
        return res;
    }
}
编辑于 2018-04-19 12:56:37 回复(0)

python O(n) solution

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, nums, k):
        # write code here
        if not k or k>len(nums):return []

        cur_max = max(nums[:k])
        max_nums = [cur_max]
        for i in range(0, len(nums) - k):
            if nums[i] == cur_max:
                cur_max = max(nums[i + 1:i + k + 1])
            elif nums[i + k] > cur_max:
                cur_max = nums[i + k]
            max_nums.append(cur_max)
        return max_nums
编辑于 2017-10-14 08:07:13 回复(4)
class Solution {
public:
    //只考虑两端增删变化的影响
    int MaxinW(const vector& num, int low, int high)
    {
        int MaxVal = INT_MIN;
        for (int j = low; j <= high; j++)
            MaxVal = max(num[j], MaxVal);
        return MaxVal;
    }
    vector maxInWindows(const vector& num, unsigned int size)
    {
        vectorres;
        int len=num.size();
        if (len len)return res;
        int MaxVal = MaxinW(num, 0, size - 1); res.push_back(MaxVal);
        for (int low = 1, high = size; high < len; low++,high++)
        {
            if (num[high] >= MaxVal)
                MaxVal = num[high];
            if (num[low - 1] == MaxVal)
                MaxVal = MaxinW(num, low, high);
            res.push_back(MaxVal);
        }
        return res;
    }
};

2.参考牛友

class Solution {
public:
    //双端队列
    //时间复杂度o(n),空间复杂度为o(n)
    //deque s中存储的是num的下标
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int>res;
        deque<int>s;
        int len=num.size();
        if (len <= 0||size<=0||size>len)return res;         
        for (int i = 0;i < len; i++)
        {
            while (!s.empty() && num[s.back()] <= num[i])//当前值比队列从后往前的大,成为下一个待选值
                s.pop_back();
            while (!s.empty()&&i - s.front() + 1>size)//最大值已不在窗口中
                s.pop_front();
            s.push_back(i);

            if (i + 1 >= size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
             res.push_back(num[s.front()]);
        }
        return res;
    }

};
编辑于 2018-12-10 16:29:50 回复(1)
一个i指示每个窗口的起点,在i循环内j遍历该窗口找出最大值。
改进的话,先找出第一个窗口中的最大值,然后窗口移动的时候观察上个窗口的最大值是否移除,如果移除就在新窗口中重新遍历计算,如没有移除就直接比较新加入窗口的数和上个窗口最大值,得出该窗口最大值。
下面是普通的解法: 
classSolution { 
public:
    vector<int> maxInWindows(constvector<int>& num, unsigned intsize)
    {
        intlen = num.size();
        vector<int> result;
        if(len < size||size==0)
            returnresult;
                     
        for(inti=0; i<=len-size; i++)
        {    
            intmax = num[i];
            for(intj = i; j< i+size;j++)
            {               
                if(num[j]>max)
                    max = num[j];
            }
            result.push_back(max);
        }       
        returnresult;
    }
};

编辑于 2015-09-02 15:33:42 回复(0)
#python2.7 O(n) 时间24ms 内存5760k
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        length = len(num)
        if size<=0 or size>length:return []
        i = 0
        ans =[max(num[:size])]
        while size+i < length:
            if num[i]<ans[-1]:
                ans.append(max([ans[-1],num[i+size]]))
            else:
                ans.append(max(num[i+1:i+size+1]))
            i+=1
        return ans

发表于 2017-12-08 10:35:35 回复(1)
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    ArrayList<Integer> maxInWindows(int [] num, int size)
    {
            int[] m_Seq=new int[size];

             ArrayList m_MaxSet=new ArrayList(); 
        
            if (num.length < size) return m_MaxSet;
        
            if (size==0) return m_MaxSet;

            for(int i=0;i<=num.length-size;i++){

                m_Seq = Arrays.copyOfRange(num,i,i+size);

                Arrays.sort(m_Seq);

                m_MaxSet.add(m_Seq[m_Seq.length-1]);

            }
        
            return m_MaxSet;
    }
}

发表于 2015-04-18 00:28:20 回复(0)
import java.util.*;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        if(num == null || size == 0 || size > num.length) {
            return new ArrayList<Integer>();
        }
        int windowNum = num.length - size + 1;
        LinkedList<Integer> list = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        int maxTmp = Integer.MIN_VALUE;
        for(int i = 0; i < windowNum; i++) {
            maxTmp = num[i];
            for (int j = 1; j < size; j++) {
                maxTmp = num[i+j] > maxTmp ? num[i+j] : maxTmp;
            }
            res.add(maxTmp);
        }
        return res;
    }
}

发表于 2018-08-14 15:37:02 回复(1)
import java.util.*;
public class Solution {
   //滑动窗口最大值
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {

        if(num ==null||size <0) return null;
        ArrayList<Integer> result = new ArrayList<>(size);
        //防止滑动窗口数值不对
        if(size ==0||num.length< size){
            return result;
        }

       //构造大顶堆
        Queue<Integer> priorityQueue = new PriorityQueue<Integer>(num.length,
new Comparator<Integer>() 
{ public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //先填充size个数值
        int i=0;
        for(;i<size;i++){
            priorityQueue.offer(num[i]);
        }

        //每次拿出堆顶,移除最前面元素并追加滑动后的元素
        for (int m =0; m +size<num.length+1; m++) {

            result.add(priorityQueue.peek());

            priorityQueue.remove(num[m]);
            //防止越界
            if(m+size == num.length){
                break;
            }
            priorityQueue.add(num[m+size]);
        }
        return result;
    }
}

编辑于 2017-09-07 10:44:24 回复(0)
/*
表达不清楚的地方,请各位批评指正!
这道题可以用双向队列解决(就是头尾都可以push,pop的队列)
时间复杂度 O(N)
方法如下几点:
    1.当我们遇到新数时候,将新的数和双向队列的末尾比较,
       若果末尾比新数小,则把末尾pop_back,
       直到末尾比新数大或者队列为空才停止;
     2.这样就保证队列元素是从头到尾降序的,
         由于队列里只有窗口内的数,所以它们其实是窗口内
         第一大,第二大…的数。
     3.保持队列里只有窗口大小的数的方法是,
         右边进一个,左边出一个。
     4.由于队列加新数时,已经删除了部分没用的数,
        所以队列头的数并不一定是窗口最左的数,
        这里有个小技巧,就是队列中存原数组的下标,
        这样既可以得到这个数,也可以判断是否是窗口
        左边的数了。
*/
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ret;
        if(num.empty() || size == 0)
            return ret;
        deque<int> deq;
        for(unsigned int i = 0;i < num.size(); ++i){
            //每当新数进来时,如果队列头部的下标是窗口最左边的下标,则删除队列头
            if(!deq.empty() && deq.front() < i - size)
                deq.pop_front();
            //队列中加入新数
            deq.push_back(i);
            //队列头部就是该窗口最大的!
            if((i + 1) >= size)
                ret.push_back(num[deq.front()]);
        }
        return ret;
    }
};

编辑于 2016-09-02 21:16:31 回复(2)