滑动窗口求最大值

第一种方法：大顶堆

第二种方法：双端队列

public class SlidingWindow {

    //输入 ：  nums = [1,3,-1,-3,5,3,6,7], 和 k = 3  
    //输出: [3,3,5,5,6,7] 
    public static void main(String[] args) {
        
       int [] arr = new int[] {1,3,-1,-3,5,3,6,7};
       int []  res = slide(arr,3);
       for(int i = 0 ; i< res.length ;i++) {
           System.out.print(res[i] + " ");
       }
       
       System.out.println();
       res = slide2(arr,3);
       for(int i = 0 ; i< res.length ;i++) {
           System.out.print(res[i] + " ");
       }
    }

    
    /**
     * 我们以数组{2,3,4,2,6,2,5,1}为例，滑动窗口大小为3，
     * 先把第一个数字2加入队列，第二个数字是3，比2大，所以2不可能是最大值，所以把2删除，3存入队列。
     * 第三个数是4，比3大，同样删3存4，此时滑动窗口已遍历三个数字，最大值4在队列的头部。
     * 第四个数字是2，比队列中的数字4小，当4滑出去以后，2还是有可能成为最大值的，因此将2加入队列尾部，此时最大值4仍在队列的头部。
     * 第五个数字是6，队列的数字4和2都比它小，所以删掉4和2，将6存入队列尾部，此时最大值6在队列头部。
     * 第六个数字是2，此时队列中的数6比2大，所以2以后还有可能是最大值，所以加入队列尾部，此时最大值6在仍然队列头部。
     * ······ 依次进行，这样每次的最大值都在队列头部。
     * 还有一点需要注意的是：如果后面的数字都比前面的小，那么加入到队列中的数可能超过窗口大小，这时需要判断滑动窗口是否包含队头的这个元素，
     * 为了进行这个检查，我们可以在队列中存储数字在数组中的下标，而不是数值，通过判断队列头部元素的下标值来确认是否将队列头部元素删除。
     */
    public static int[] slide2(int [] nums , int k) {
            int[] res = new int[nums.length - k + 1];
            int index = 0 ;
            Deque<Integer> queue=new LinkedList<>();
            for(int i=0;i<nums.length;i++){
                //当前值大于之前的值，之前的不可能是最大值，循环删掉队列末尾的值
                while(!queue.isEmpty() && nums[i]>=nums[queue.getLast()]) {
                     queue.removeLast();
                } 
                queue.add(i);
                //检查队列的头部元素是否超过范围了，超过范围就移除出队列
                while(!queue.isEmpty() && queue.peekFirst()<i-2) {
                      queue.pollFirst();
                } 
                //添加到res
                if(i >= 2){ 
                    res[index++] = nums[queue.peekFirst()];
                }
            }
            return res;
    }
    
    
    /**
     * 
     * 大顶堆会把如入的元素进行排序，堆顶元素始终是最大值，当新加入元素后，判断堆顶元素下标是否超过范围了，超过范围弹出就可以
     * 这个方法中的数字2，是为了好理解写的固定值
     */
    public static int[] slide(int []  nums , int k) {
        //建立一个大顶堆，priorityQueue是动态数组实现的，内部会自动扩容，所以有个可以传入数量的构造方法并不起作用，即不能构建固定大小的大顶堆
        PriorityQueue<Item> queue = new PriorityQueue<>(new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o2.value - o1.value;
            }
        });
        int[] res = new int[nums.length - k + 1];//存放结果
        int index = 0;
        for(int i=0;i<nums.length;i++) {
             queue.add(new Item(nums[i],i));
             if(i < 2 ) {
                 continue;
             }
            //从下标3开始，每进来一个数，判断堆顶的数据的下标是不是在给定的窗口范围内
            if(i > 2) {
                Item item = queue.peek();
                while(item.index < i-2) {
                    queue.poll();
                    item =queue.peek();
                }
            }
            //把堆顶元素放入res中
            res[index++] = queue.peek().value;
        }
        return res;
    }
    
    
    public static class Item{
        int  value;
        int  index;
        public Item(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
    
}