滑动窗口的最大值 - 数据结构 - 机器学习

1272 人阅读 | 时间：2021年01月15日 01:22

滑动窗口的最大值

12530 人参与 2019年03月20日 11:10 分类 : 面试笔试评论

题目描述

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

方法一：

一个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;
    }
};

方法二：

/*

表达不清楚的地方，请各位批评指正！

这道题可以用双向队列解决(就是头尾都可以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;
    }
};

其他汇总：

//滑动窗口可用队列进行实现

//逐个进入并取最大值，始终保证size大小的数

第一种解法：
        Queue<Integer> queue=new LinkedList();
        int index=0;
        int arrayIndex=0;
        int max=num[0];
        while(index<size && arrayIndex<num.length)
        {
            queue.offer(num[arrayIndex]);
           if(num[arrayIndex]>max){
                max=num[arrayIndex];
            }
             arrayIndex++;
            index++;
            if(queue.size()==size){
                index=0;
                int rmElement=queue.poll();
                list.add(max);
                if(rmElement==max ){
                    //如果最大值移除的话，找到剩余队列中最大值作为当前最大值
                    if(!queue.isEmpty()){
                    max=queue.peek();
                    for(Integer i:queue){
                        if(max<i){
                            max=i;
                        }
                    }
                    }else{ //如果队列为空，则重置最大值
                        max=Integer.MIN_VALUE;
                    }
                }
                 
            }
                   
第二种解法：
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(size==0||num.length==0){
            return list;
        }
      
        for(int i=0;i<=num.length-size;i++){
            int max=num[i];
//每个元素和 后面size-1个元素进行比较 每次取出size个元素中最大的一个 
            for(int j=1;j<size;j++){
                if(max<num[j+i]){
                    max=num[j+i];
                }
            }
            list.add(max);
        }
         
                 
         return list;
 
//第三种解法：
    //双向队列的方法，队列只存最大值 和依次小于最大值的元素的 坐标
    //在队列首部存放当前最大值的坐标，如果后续加进来的元素比现在的队尾元素小，则加入
    //如果当前队尾的元素 比要加入的 新元素的 小，则移除这些队尾元素
  
        //如果当前坐标i+1>=size说明 窗口已经覆盖了三个元素以上，可以拿最大值了
        //双向队列用LinkedList
        LinkedList<Integer> indexQueue=new LinkedList();
        for(int i=0;i<=num.length-1;i++){
    //将队列从尾部开始 小于新加入元素的 元素坐标都移除，因为此时他们已经不可能是窗口最大值了
    while(!indexQueue.isEmpty() && num[i]> num[indexQueue.getLast()]){
                indexQueue.removeLast();
            }
            indexQueue.addLast(i);
//队首元素 的有效期 即 它为最大元素的窗口 是在 他的坐标index +size区间内，超过这个
区间就移除掉这个当前最大值 即当前队首元素
              if(indexQueue.getFirst()+size==i){
                indexQueue.removeFirst();
            }
//当i+1<size时候说明窗口还没覆盖到3个元素，还没找到窗口覆盖的最大值
            if(i+1>=size){
                result.add(num[indexQueue.getFirst()]);
            }
             
 }

来源：我是码农，转载请保留出处和链接！