java 实现滑动窗口的最大值算法

╰半橙微兮° 2022-10-06 08:53 125阅读 0赞

## 描述 ##

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,5,2,6,2,4,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{5, 5, 6, 6, 6, 4\}； 针对数组\{2,3,5,2,6,2,4,1\}的滑动窗口有以下6个： \{\[2,3,5\],2,6,2,6,1\}， \{2,\[3,5,2\],6,2,4,1\}， \{2,3,\[5,2,6\],2,4,1\}， \{2,3,5,\[2,6,2\],4,1\}， \{2,3,5,2,\[6,2,4\],1\}， \{2,3,5,2,6,\[2,4,1\]\}。

窗口大于数组长度的时候，返回空

输入：

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

输出：

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

核心代码实现：

//思路：用一个大根堆，保存当前滑动窗口中的数据。滑动窗口每次移动一格，就将前面一个数出堆，后面一个数入堆。
    
    public class JZ64HuaDongChuangKouZuiDaZhi {
    
        public static void main(String[] args) {
            int[] num = {2,3,5,2,6,2,4,1};
            int size = 3;
            ArrayList<Integer> list = maxInWindows(num, size);
            System.out.println(list.toString());
        }
    
    
        public static PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>((o1,o2)->o2-o1);//大根堆
        public static ArrayList<Integer> result = new ArrayList<Integer>();//保存结果的集合
    
        private static ArrayList<Integer> maxInWindows(int[] num, int size) {
            if(num == null || num.length < 1 || size < 1 || size > num.length){
                return result;
            }
            int count;
            //初始化滑动窗口
            for(count = 0;count < size;count++){
                maxQueue.offer(num[count]);
            }
            //对每次操作，找到最大值（用优先队列的大根堆），然后向后滑动（出堆一个，入堆一个）
            while (count < num.length){
                result.add(maxQueue.peek());
                maxQueue.remove(num[count - size]);
                maxQueue.offer(num[count]);
                count++;
            }
    
            result.add(maxQueue.peek());//最后一次入堆后没保存结果，这里额外做一次即可
    
            return result;
    
        }
     
    }

执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

在牛客网上这是属于较难的算法题，其实它有多种解决方案，此处示例一种，抛砖引玉，举一反三，大家多多练习，扎实coding能力，更进一步。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/dfbb25c9184549cf8d7c856ee2451975.png