推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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 Solution {
   
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
   
        
    }
}

**参考思路：**最大堆

  1. 先排除一下特殊情况。
  2. 构建一个最大堆。
  3. 将数组中的 0~size 存入最大堆中，并将堆顶元素存入结果集合中。
  4. 固定最大堆的大小为 size， 每次移除最大堆中上一次存入的元素，并存入下一个元素，然后每次将堆顶元素存入到集合中。
  5. 遍历完数组之后，输出最终结果。

参考实现：

import java.util.*;
public class Solution {
   
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
   
        //创建一个存储结果的集合
        ArrayList<Integer> result = new ArrayList<>();
        //如果滑动窗口长度大于数组长度或者小于1，直接输出空的result。
        if (size > num.length || size < 1) {
   
            return result;
        }
        //构建一个大顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<>((o1,o2) -> o2 - o1);
        
        //将初始窗口中的值加到大顶堆汇中去
        for (int i = 0; i < size; i++) {
   
            heap.add(num[i]);
        }
        //将大顶堆中的堆顶元素存入到result结果中,也就是第一个窗口中的最大值
        result.add(heap.peek());
        //将最大堆的大小固定为size，每次将前一个元素移除，将后一个元素添加进去，然后将每次的堆顶元素添加到result结果中。
        for(int i = 0, j = i + size; j < num.length; i++,j++) {
   
            heap.remove(num[i]);
            heap.add(num[j]);
            result.add(heap.peek());
        }
        //返回最终结果
        return result;
    }
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！