滑动窗口的最大值

题目描述

解题思路

最大堆

使用Java的优先队列（也就是堆），我们可以使用最大堆（PriorityQueue默认是最小堆，构建最大堆只需要在构建时传入一个 comparator 即可），在滑动窗口滑动时，将当前元素加入最大堆中，堆顶的元素即是最大值。

public ArrayList<Integer> maxInWindows(int[] nums, int size){
    ArrayList<Integer> ret = new ArrayList<>();
    if(nums==null || nums.length==0 || size==0)
        return ret;
    PriorityQueue<Integer> heap = new PriorityQueue<>((o1,o2)->o2-o1);
    for(int i=0; i<size; i++){
        heap.add(nums[i]);
    }
    ret.add(heap.peek());
    for(int i=0, j=i+size; j<nums.length; i++,j++){
        heap.remove(nums[i]);
        heap.add(nums[j]);
        ret.add(heap.peek());
    }
    return ret;
}

双端队列

可以使用双端队列，队列中之存放当前元素的下标，设新来的元素为k，如果前面的元素比k小，直接把前面的删除（因为不可能成为后面窗口的最大值），如果前面的元素比 k 大，判断是否还在窗口范围内，不在则移除。

1. 先判断当前队列是否为空，如果不空而且当前元素比队列中尾部的元素大，将队列元素的尾端弹出；
2. 判断队列头元素（存的是下标）是否还在滑动窗口中，不在则把头元素移除。

public ArrayList<Integer> maxInWindows(int[] nums, int size){
    ArrayList<Integer> ret = new ArrayList<>();
    if(nums==null || nums.length==0 || size==0)
        return ret;
    Deque<Integer> queue = new LinkedList<>();
    for(int i=0; i<nums.length; i++){
        while(!queue.isEmpty() && nums[i]>=nums[queue.getLast()])
            queue.pollLast();
        while(!queue.isEmpty() && queue.getFirst()<i-(size-1))
            queue.pollFirst();
        queue.offerLast(i);
        if(i+1>=size){
            ret.add(nums[queue.getFirst()]);
        }
    }
    return ret;
}