描述

给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

数据范围：1<=size<=n<=10000

元素值范围：|val|<=10000

示例

• 输入：数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3
• 输出：{4,4,6,6,6,5}，一共存在6个滑动窗口

思路1：双重遍历

双重遍历找到每个窗口的最大值。时间复杂度O(nk)，k为窗口大小（会超时）

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        for(int i = 0; i <= num.length - size; i++) {
            int max = num[i];
            for(int j = i + 1; j < i + size; j++) {
                max = Math.max(max, num[j]);
            }
            ret.add(max);
        }
        return ret;
    }
}

思路2：使用大顶堆+Pair

使用大顶堆存储值和索引，当根节点"过期"时推出，直到根节点在滑动窗口范围内

Pair也可以改为容量为2的数组

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        PriorityQueue<Pair> queue = new PriorityQueue<>((n1, n2) -> n2.value - n1.value);
        //先把第一个窗口的值推进堆中，避免在循环中判断i > size - 1
        for(int i = 0; i < size; i++) {
            queue.offer(new Pair(num[i], i));
        }
        //从窗口右边开始往后移动
        for(int i = size - 1; i < num.length; i++) {
            queue.offer(new Pair(num[i], i));
            while(queue.peek().index <= i - size) {
                queue.poll();
            }
            ret.add(queue.peek().value);
        }
        return ret;
    }
    
    static class Pair {
        int value;
        int index;
        Pair(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}

思路3：大顶堆优化版

1. 可以优化掉Pair对象，只存储索引，比较的时候从数组中取值
2. 堆中存放了很多没用的元素，当最新的值大于根元素时，可以进行清理
3. 也可以每次循环remove掉超出窗口的索引

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        //从数组中取值进行比较num[n2] - num[n1]
        PriorityQueue<Integer> queue = new PriorityQueue<>((n1, n2) -> num[n2] - num[n1]);
        //先offer一个，就不用在循环中判空了
        queue.offer(0);
        for(int i = 1; i < size; i++) {
            if(num[queue.peek()] < num[i]) {
                queue.clear();
            } 
            queue.offer(i);
        }
        for(int i = size - 1; i < num.length; i++) {
            if(num[queue.peek()] < num[i]) {
                //清除无用元素
                queue.clear();
                queue.offer(i);
            } else {
                queue.offer(i);
                while(queue.peek() <= i - size) {
                    queue.poll();
                }
            }
            ret.add(num[queue.peek()]);
        }
        return ret;
    }
}

思路4：单调队列

类似大顶堆，只不过换成了队列结构，保证队列单调递减：即队头是最大元素，新元素不断和尾部元素比较，如果大于尾部，则移除尾部元素。

优化掉了大顶堆的查找、插入、删除效率，避免不断调整堆结构

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < num.length; i++) {
            while(!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            //每次只会有一个过期
            if(deque.peekFirst() <= i - size) {
                deque.pollFirst();
            }
            if(i >= size - 1) {
                ret.add(num[deque.peekFirst()]);
            }
        }
        return ret;
    }
}