求滑动窗口的最大值

素颜马尾好姑娘i 2023-02-09 05:27 146阅读 0赞

## 题目描述 ##

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

## 解法一： ##

可以先简单地将滑动窗口当成一个数组，根据滑动窗口的特点，每次移动并不只是窗口的首部start或是尾部end单独移动，为了实现窗口的整体性，可以将窗口的移动size单位认为**start和end同时移动了size单位**。基于此，有如下的代码解决方案：

public static ArrayList<Integer> maxInWindows(int [] num, int size) { 
            //确定滑动窗口
            int start = 0;
            int end = start + size - 1;
            ArrayList<Integer> window = new ArrayList<>();
            ArrayList<Integer> maxList = new ArrayList<>();
            if (size == 0){ 
                return maxList;
            }
            while (end != num.length){ 
                window = new ArrayList<>();
                int temp = start;
                for (int i = 0 ;i < size; i++){ 
                    window.add(num[temp]);
                    temp++;
                }
                int max = Collections.max(window);
                maxList.add(max);
                start++;
                end++;
            }
            return maxList;
        }

## 解法二： ##

因为滑动窗口的移动是头部数据移除，尾部数据添加的形式，所以可以把滑动窗口认为是一个**双端队列**。根据例子，具体的移动如下表所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDUxOTIz_size_16_color_FFFFFF_t_70]  
实现代码：

public ArrayList<Integer> maxInWindows(int [] num, int size){ 
            /* 思路：用双端队列实现 */
            ArrayList<Integer> res=new ArrayList<>();
            if(num==null || num.length<1 || size<=0 || size>num.length)
                return res;
            Deque<Integer> queue=new LinkedList<>();
            for(int i=0;i<num.length;i++){ 
                while(!queue.isEmpty() && queue.peek()<i-size+1) //超出范围的去掉
                     queue.poll();
                //当前值大于之前的值，之前的不可能是最大值，可以删掉
                while(!queue.isEmpty() && num[i]>=num[queue.getLast()]) 
                     queue.removeLast();
                queue.add(i);
                if(i>=size-1){  //此时开始是第一个滑动窗口
                    res.add(num[queue.peek()]);
                }
            }
            return res;
        }

参考博客：  
https://www.cnblogs.com/gzshan/p/10904273.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDUxOTIz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200518144948883.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDUxOTIz,size_16,color_FFFFFF,t_70