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]}。
窗口大于数组长度的时候，返回空
示例1
输入
[2,3,4,2,6,2,5,1],3
返回值
[4,4,6,6,6,5]

解题思路
思想：
大顶堆和双指针进行结合
步骤：
1.初始化i=0,j=size（i和j之间为一个滑动窗口，之后一块平移到最后）
2.对于i和j之间的元素，只需要求最大值，所以建一个大顶堆
3.取出堆顶元素（最大值），之后清空堆（清空可以避免每次都创建堆）
注意：PriorityQueue默认创建的是小顶堆，记得修改比较器

Java代码

import java.util.*;
public class Solution {
    //大顶堆和双指针
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> list=new ArrayList<>();
        if(size>num.length || size <=0) return list; 
        PriorityQueue<Integer> max_heap=new PriorityQueue<Integer>(new Comparator<Integer>(){
                @Override
                public int compare(Integer o1,Integer o2 ){
                    return o2-o1;
                }
            });//创建大顶堆，默认是小顶堆
        for(int i=0,j=size;j<=num.length;i++,j++){
            for(int m=i;m<j;m++){
                max_heap.offer(num[m]);
            }
            list.add(max_heap.peek());
            max_heap.clear();
        }
        return list;
    }
}